Arrow Research search

Author name cluster

Michal Feldman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

45 papers
2 author rows

Possible papers

45

AAAI Conference 2025 Conference Paper

Proportionally Fair Makespan Approximation

  • Michal Feldman
  • Jugal Garg
  • Vishnu V. Narayan
  • Tomasz Ponitka

We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the egalitarian social cost in the fair division of chores. The two prevalent fairness notions in the fair division literature are envy-freeness and proportionality. Prior work has established that no envy-free mechanism can provide better than an Ω(log m / log log m)-approximation to the optimal makespan, where m is the number of machines, even when payments to the machines are allowed. In strong contrast to this impossibility, our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a 3/2-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. We conclude with important directions for future research concerning other fairness notions, including relaxations of envy-freeness. Notably, we show that the technique leading to the impossibility result for envy-freeness does not extend to its relaxations.

PDF Details DOI

AAAI Conference 2024 Conference Paper

On Optimal Tradeoffs between EFX and Nash Welfare

  • Michal Feldman
  • Simon Mauras
  • Tomasz Ponitka

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal of this work is to characterize the tradeoffs between two well-studied measures of fairness and efficiency --- envy freeness up to any item (EFX) for fairness, and Nash welfare for efficiency --- by saying, for given constants α and β, whether there exists an α-EFX allocation that guarantees a β-fraction of the maximum Nash welfare (β-MNW). For additive valuations, we show that for any α ∈ [0,1], there exists a partial allocation that is α-EFX and 1/(α+1)-MNW. This tradeoff turns out to be tight (for every α) as demonstrated by an impossibility result that we give. We also show that for α ∈ [0, φ-1 ≃ 0.618] these partial allocations can be turned into complete allocations where all items are assigned. Furthermore, for any α ∈ [0, 1/2], we show that the tight tradeoff of α-EFX and 1/(α+1)-MNW with complete allocations holds for the more general setting of subadditive valuations. Our results improve upon the current state of the art, for both additive and subadditive valuations, and match the best-known approximations of EFX under complete allocations, regardless of Nash welfare guarantees. Notably, our constructions for additive valuations also provide EF1 and constant approximations for maximin share guarantees.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Pandora’s Problem with Deadlines

  • Ben Berger
  • Tomer Ezra
  • Michal Feldman
  • Federico Fusco

Pandora’s problem is a fundamental model that studies optimal search under costly inspection. In the classic version, there are n boxes, each associated with a known cost and a known distribution over values. A strategy inspects the boxes sequentially and obtains a utility that equals the difference between the maximum value of an inspected box and the total inspection cost. Weitzman (1979) presented a surprisingly simple strategy that obtains the optimal expected utility. In this work we introduce a new variant of Pandora’s problem in which every box is also associated with a publicly known deadline, indicating the final round by which its value may be chosen. This model captures many real-life scenarios where alternatives admit deadlines, such as candidate interviews and college admissions. Our main result is an efficient threshold-based strategy that achieves a constant approximation relative to the performance of the optimal strategy for the deadlines setting.

PDF Details DOI

SODA Conference 2023 Conference Paper

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

  • Tomer Ezra
  • Michal Feldman
  • Nikolai Gravin
  • Zhihao Gavin Tang

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.

Details

FOCS Conference 2023 Conference Paper

Constant Approximation for Private Interdependent Valuations

  • Alon Eden
  • Michal Feldman
  • Kira Goldner
  • Simon Mauras
  • Divyarthi Mohan

The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_{1}, \ldots, s_{n}$ of the n bidders and public valuation functions $v_{i}\left(s_{1}, \ldots, s_{n}\right)$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O\left(\log ^{2} n\right)$-approximation for SOS valuations. In this paper we show that this setting admits a constant factor approximation, settling the open question raised by Eden et al. (2022).

Details

STOC Conference 2023 Conference Paper

Multi-agent Contracts

  • Paul Dütting
  • Tomer Ezra
  • Michal Feldman
  • Thomas Kesselheim

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 Ω(√ 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.

Details

JAIR Journal 2023 Journal Article

On Fair Division under Heterogeneous Matroid Constraints

  • Amitay Dror
  • Michal Feldman
  • Erel Segal-Halevi

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints or allow free disposal of items. An open problem is the existence of EF1 complete allocations among agents who differ both in their valuations and in their feasibility constraints. In this work, we make progress on this problem by providing positive and negative results for several matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous (non-identical) binary valuations and partition matroids with heterogeneous capacities; (ii) two agents with heterogeneous additive valuations and partition matroids with heterogeneous capacities; and (iii) three agents with heterogeneous binary valuations and identical base-orderable matroid constraints.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Almost Full EFX Exists for Four Agents

  • Ben Berger
  • Avi Cohen
  • Michal Feldman
  • Amos Fiat

The existence of EFX allocations of goods is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. It is also known that EFX exists if one can leave n − 1 items unallocated, where n is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.

PDF Details

AAAI Conference 2022 Conference Paper

Two-Price Equilibrium

  • Michal Feldman
  • Galia Shabtai
  • Aner Wolfenfeld

Walrasian equilibrium is a prominent market equilibrium notion, but rarely exists in markets with indivisible items. We introduce a new market equilibrium notion, called two-price equilibrium (2PE). A 2PE is a relaxation of Walrasian equilibrium, where instead of a single price per item, every item has two prices: one for the item’s owner and a (possibly) higher one for all other buyers. Thus, a 2PE is given by a tuple (S, p̂, p̌) of an allocation S and two price vectors p̂, p̌, where every buyer i is maximally happy with her bundle Si, given prices p̌ for items in Si and prices p̂ for all other items. 2PE generalizes previous market equilibrium notions, such as conditional equilibrium, and is related to relaxed equilibrium notions like endowment equilibrium. We define the discrepancy of a 2PE — a measure of distance from Walrasian equilibrium — as the sum of differences p̂j −p̌j over all items (normalized by social welfare). We show that the social welfare degrades gracefully with the discrepancy; namely, the social welfare of a 2PE with discrepancy d is at least a fraction 1 d+1 of the optimal welfare. We use this to establish welfare guarantees for markets with subadditive valuations over identical items. In particular, we show that every such market admits a 2PE with at least 1/7 of the optimal welfare. This is in contrast to Walrasian equilibrium or conditional equilibrium which may not even exist. Our techniques provide new insights regarding valuation functions over identical items, which we also use to characterize instances that admit a WE.

PDF Details

FOCS Conference 2021 Conference Paper

Combinatorial Contracts

  • Paul Dütting
  • Tomer Ezra
  • Michal Feldman
  • Thomas Kesselheim

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.

Details

IJCAI Conference 2021 Conference Paper

On a Competitive Secretary Problem with Deferred Selections

  • 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 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.

PDF Details DOI

AAAI Conference 2021 Conference Paper

On Fair Division under Heterogeneous Matroid Constraints

  • Amitay Dror
  • Michal Feldman
  • Erel Segal-Halevi

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents’ feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise poly-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroids.

PDF Details

AAAI Conference 2021 Conference Paper

PoA of Simple Auctions with Interdependent Values

  • Alon Eden
  • Michal Feldman
  • Inbal Talgam-Cohen
  • Ori Zviran

We expand the literature on the price of anarchy (PoA) of simultaneous item auctions by considering settings with correlated values; we do this via the fundamental economic model of interdependent values (IDV). It is well-known that in multi-item settings with private values, correlated values can lead to bad PoA, which can be polynomially large in the number of agents n. In the more general model of IDV, we show that the PoA can be polynomially large even in singleitem settings. On the positive side, we identify a natural condition on information dispersion in the market, which enables good PoA guarantees. Under this condition, we show that for single-item settings, the PoA of standard mechanisms degrades gracefully. For settings with multiple items we show a separation between two domains: If there are more buyers, we devise a new simultaneous item auction with good PoA, under limited information asymmetry. To the best of our knowledge, this is the first positive PoA result for correlated values in multi-item settings. The main technical difficulty in establishing this result is that the standard tool for establishing PoA results — the smoothness framework — is unsuitable for IDV settings, and so we must introduce new techniques to address the unique challenges imposed by such settings. In the domain of more items, we establish impossibility results even for surprisingly simple scenarios.

PDF Details

AAAI Conference 2021 Conference Paper

Simultaneous 2nd Price Item Auctions with No-Underbidding

  • Michal Feldman
  • Galia Shabtai

We study the price of anarchy (PoA) of simultaneous 2nd price auctions (S2PA) under a new natural condition of no underbidding, meaning that agents never bid on items less than their marginal values. We establish improved (mostly tight) bounds on the PoA of S2PA under no underbidding for different valuation classes (including unit-demand, submodular, XOS, subadditive, and general monotone valuations), in both full-information and incomplete information settings. To derive our results, we introduce a new parameterized property of auctions, termed (γ, δ)-revenue guaranteed, which implies a PoA of at least γ/(1+δ). Via extension theorems, this guarantee extends to coarse correlated equilibria (CCE) in full information settings, and to Bayesian PoA (BPoA) in settings with incomplete information and arbitrary (correlated) distributions. We then show that S2PA are (1, 1)-revenue guaranteed with respect to bids satisfying no underbidding. This implies a PoA of at least 1/2 for general monotone valuation, which extends to BPOA with arbitrary correlated distributions. Moreover, we show that (λ, µ)-smoothness combined with (γ, δ)-revenue guaranteed guarantees a PoA of at least (γ + λ)/(1 + δ + µ). This implies a host of results, such as a tight PoA of 2/3 for S2PA with submodular (or XOS) valuations, under no overbidding and no underbidding. Beyond establishing improved bounds for S2PA, the no underbidding assumption sheds new light on the performance of S2PA relative to simultaneous 1st price auctions.

PDF Details

AAAI Conference 2020 Conference Paper

Designing Committees for Mitigating Biases

  • Michal Feldman
  • Yishay Mansour
  • Noam Nisan
  • Sigal Oren
  • Moshe Tennenholtz

It is widely observed that individuals prefer to interact with others who are more similar to them (this phenomenon is termed homophily). This similarity manifests itself in various ways such as beliefs, values and education. Thus, it should not come as a surprise that when people make hiring choices, for example, their similarity to the candidate plays a role in their choice. In this paper, we suggest that putting the decision in the hands of a committee instead of a single person can reduce this bias. We study a novel model of voting in which a committee of experts is constructed to reduce the biases of its members. We first present voting rules that optimally reduce the biases of a given committee. Our main results include the design of committees, for several settings, that are able to reach a nearly optimal (unbiased) choice. We also provide a thorough analysis of the trade-offs between the committee size and the obtained error. Our model is inherently different from the well-studied models of voting that focus on aggregation of preferences or on aggregation of information due to the introduction of similarity biases.

PDF Details

AAMAS Conference 2019 Conference Paper

Efficient Allocation of Free Stuff

  • Yossi Azar
  • Allan Borodin
  • Michal Feldman
  • Amos Fiat
  • Kineret Segal

We study online matching settings with selfish agents when everything is free. Inconsiderate agents break ties arbitrarily amongst equal maximal value available choices, even if the maximal value is equal to zero. Even for the simplest case of zero/one valuations, where agents arrive online in an arbitrary order, and agents are restricted to taking at most one item, the resulting social welfare may be negligible for a deterministic algorithm. This may be surprising when contrasted with the 1/2 approximation of the greedy algorithm, analogous to this setting, except that agents are considerate (i. e. , they don’t take zero-valued items). We overcome this challenge by introducing a new class of algorithms, which we refer to as prioritization algorithms. We show that upgrading a random subset of the agents to “business class" already improves the approximation to a constant. For more general valuations, we achieve a constant approximation using logn priority classes, when the valuations are known in advance. We extend these results to settings where agents have additive valuations and are restricted to taking up to some q ≥ 1 items. Our results are tight up to a constant.

PDF

FOCS Conference 2019 Conference Paper

Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers

  • Tomer Ezra
  • Michal Feldman
  • Eric Neyman
  • Inbal Talgam-Cohen
  • S. Matthew Weinberg

We study the communication complexity of welfare maximization in combinatorial auctions with m items and two players with subadditive valuations. We show that outperforming the trivial 1/2-approximation requires exponential communication, settling an open problem of Dobzinski, Nisan and Schapira [STOC’05, MOR’10] and Feige [STOC’06, SICOMP ’09]. To derive our results, we introduce a new class of subadditive functions that are “far from” fractionally subadditive (XOS) functions, and establish randomized communication lower bounds for a new “near-EQUALITY” problem, both of which may be of independent interest.

Details

STOC Conference 2017 Conference Paper

Approximate modularity revisited

  • Uriel Feige
  • Michal Feldman
  • Inbal Talgam-Cohen

Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as algorithmic game theory, and allow for improved optimization algorithms. It is natural to ask (e.g., in the context of data driven optimization) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions. One question that we address is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive (in a precise formal sense) as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem. Another question that we address is that of how to learn a linear function h that is close to an approximately linear function f , while querying the value of f on only a small number of sets. We present a deterministic algorithm that makes only linearly many (in the number of items) nonadaptive queries, by this improving over a previous algorithm of Chierichetti, Das, Dasgupta and Kumar [2015] that is randomized and makes more than a quadratic number of queries. Our learning algorithm is based on a Hadamard transform.

Details

FOCS Conference 2017 Conference Paper

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

  • Paul Dütting
  • Michal Feldman
  • Thomas Kesselheim
  • Brendan Lucier

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

Details

NeurIPS Conference 2016 Conference Paper

Online Pricing with Strategic and Patient Buyers

  • Michal Feldman
  • Tomer Koren
  • Roi Livni
  • Yishay Mansour
  • Aviv Zohar

We consider a seller with an unlimited supply of a single good, who is faced with a stream of $T$ buyers. Each buyer has a window of time in which she would like to purchase, and would buy at the lowest price in that window, provided that this price is lower than her private value (and otherwise, would not buy at all). In this setting, we give an algorithm that attains $O(T^{2/3})$ regret over any sequence of $T$ buyers with respect to the best fixed price in hindsight, and prove that no algorithm can perform better in the worst case.

PDF Details

AAAI Conference 2016 Conference Paper

Variations on the Hotelling-Downs Model

  • Michal Feldman
  • Amos Fiat
  • Svetlana Obraztsova

In this paper we expand the standard Hotelling-Downs model (Hotelling 1929; Downs 1957) of spatial competition to a setting where clients do not necessarily choose their closest candidate (retail product or political). Specifically, we consider a setting where clients may disavow all candidates if there is no candidate that is sufficiently close to the client preferences. Moreover, if there are multiple candidates that are sufficiently close, the client may choose amongst them at random. We show the existence of Nash Equilibria for some such models, and study the price of anarchy and stability in such scenarios.

PDF Details

AAAI Conference 2015 Conference Paper

A Unifying Hierarchy of Valuations with Complements and Substitutes

  • Uriel Feige
  • Michal Feldman
  • Nicole Immorlica
  • Rani Izsak
  • Brendan Lucier
  • Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MPH-m (where m is the total number of items) captures all monotone functions. The lowest level, MPH-1, captures all monotone submodular functions, and more generally, the class of functions known as XOS. Every monotone function that has a positive hypergraph representation of rank k (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in MPH-k. Every monotone function that has supermodular degree k (in the sense defined by Feige and Izsak [ITCS 2013]) is in MPH-(k+1). In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of MPH-k. One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MPH hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k + 1 if all players hold valuation functions in MPH-k. The other is an upper bound of 2k on the price of anarchy of simultaneous first price auctions.

PDF Details

SODA Conference 2015 Conference Paper

Combinatorial Auctions via Posted Prices

  • Michal Feldman
  • Nikolai 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 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.

Details

AAAI Conference 2015 Conference Paper

Do Capacity Constraints Constrain Coalitions?

  • Michal Feldman
  • Ofir Geri

We study strong equilibria in symmetric capacitated costsharing games. In these games, a graph with designated source s and sink t is given, and each edge is associated with some cost. Each agent chooses strategically an s-t path, knowing that the cost of each edge is shared equally between all agents using it. Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios. In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games. This combination gives rise to new phenomena that do not occur in the previous variants. Our contribution is two-fold. First, we provide a topological characterization of networks that always admit a strong equilibrium. Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures. Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.

PDF Details

IJCAI Conference 2015 Conference Paper

How Robust Is the Wisdom of the Crowds?

  • Noga Alon
  • Michal Feldman
  • Omer Lev
  • Moshe Tennenholtz

We introduce the study of adversarial effects on wisdom of the crowd phenomena. In particular, we examine the ability of an adversary to influence a social network so that the majority of nodes are convinced by a falsehood, using its power to influence a certain fraction, µ 0. 5. When we examine expander graphs as well as random graphs we prove such bounds even for stronger adversaries, who are able to pick and choose not only who the experts are, but also which ones of them would communicate the wrong values, as long as their proportion is 1 − p. Furthermore, we study different propagation models and their effects on the feasibility of obtaining the true value for different adversary types.

PDF Details

IJCAI Conference 2015 Conference Paper

Implementing the Wisdom of Waze

  • Shoshana Vasserman
  • Michal Feldman
  • Avinatan Hassidim

We study a setting of non-atomic routing in a network of m parallel links with asymmetry of information. While a central entity (such as a GPS navigation system) — a mediator hereafter — knows the cost functions associated with the links, they are unknown to the individual agents controlling the flow. The mediator gives incentive compatible recommendations to agents, trying to minimize the total travel time. Can the mediator do better than when agents minimize their travel time selfishly without coercing agents to follow his recommendations? We study the mediation ratio: the ratio between the mediated equilibrium obtained from an incentive compatible mediation protocol and the social optimum. We find that mediation protocols can reduce the efficiency loss compared to the full revelation alternative, and compared to the non mediated Nash equilibrium. In particular, in the case of two links with affine cost functions, the mediation ratio is at most 8/7, and remains strictly smaller than the price of anarchy of 4/3 for any fixed m. Yet, it approaches the price of anarchy as m grows. For general (monotone) cost functions, the mediation ratio is at most m, a significant improvement over the unbounded price of anarchy.

PDF Details

STOC Conference 2013 Conference Paper

Simultaneous auctions are (almost) efficient

  • Michal Feldman
  • Hu Fu 0001
  • Nikolai Gravin
  • Brendan Lucier

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.

Details

AAMAS Conference 2012 Conference Paper

Mastering multi-player games

  • Yossi Azar
  • Uriel Feige
  • Michal Feldman
  • Moshe Tennenholtz

We consider multi-player games, and the guarantees that a master player that plays on behalf of a set of players can offer them, without making any assumptions on the rationality of the other players. Our model consists of an $(n+1)$-player game, with $m$ strategies per player, in which a \emph{master} player $M$ forms a coalition with nontransferable utilities among $n$ players, and the remaining player is called the {\em independent} player. Existentially, it is shown that every game admits a \emph{product-minimax-safe} strategy for $M$ -- a strategy that guarantees for every player in $M$'s coalition an expected value of at least her \emph{product minimax value} (which is at least as high as her minimax value and is often higher). Algorithmically, for any given vector of values for the players, one can decide in polytime whether it can be ensured by $M$, and if so, compute a mixed strategy that guarantees it. In symmetric games, a product minimax strategy for $M$ can be computed efficiently, even without being given the safety vector. We also consider the performance guarantees that $M$ can offer his players in repeated settings. Our main result here is the extension of the oblivious setting of Feldman, Kalai and Tennenholtz, showing that in every symmetric game, a master player who never observes a single payoff can guarantee for each of its players a {\em similar} performance to that of the independent player, even if the latter gets to choose the payoff matrix after the fact.

PDF

AAAI Conference 2012 Conference Paper

On Maxsum Fair Cake Divisions

  • Steven Brams
  • Michal Feldman
  • John Lai
  • Jamie Morgenstern
  • Ariel Procaccia

We consider the problem of selecting fair divisions of a heterogeneous divisible good among a set of agents. Recent work (Cohler et al. , AAAI 2011) focused on designing algorithms for computing maxsum—social welfare maximizing—allocations under the fairness notion of envyfreeness. Maxsum allocations can also be found under alternative notions such as equitability. In this paper, we examine the properties of these allocations. In particular, we provide conditions for when maxsum envy-free or equitable allocations are Pareto optimal and give examples where fairness with Pareto optimality is not possible. We also prove that maxsum envy-free allocations have weakly greater welfare than maxsum equitable allocations when agents have structured valuations, and we derive an approximate version of this inequality for general valuations.

PDF Details

AAMAS Conference 2012 Conference Paper

Stablity Scores: Measuring Coalitional Stability

  • Michal Feldman
  • Reshef Meir
  • Moshe Tennenholtz

We introduce a measure for the level of stability against coalitional deviations, called \emph{stability scores}, which generalizes widely used notions of stability in non-cooperative games. We use the proposed measure to compare various Nash equilibria in congestion games, and to quantify the effect of game parameters on coalitional stability. For our main results, we apply stability scores to analyze and compare the Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG) ad auctions. We show that while a central result of the ad auction literatures is that the GSP and VCG auctions implement the same outcome in one of the equilibria of GSP, the GSP outcome is far more stable. Finally, a modified version of VCG is introduced, which is group strategy-proof, and thereby achieves the highest possible stability score.

PDF

UAI Conference 2011 Conference Paper

Solving Cooperative Reliability Games

  • Yoram Bachrach
  • Reshef Meir
  • Michal Feldman
  • Moshe Tennenholtz

Cooperative games model the allocation of profit from joint actions, following considerations such as stability and fairness. We propose the reliability extension of such games, where agents may fail to participate in the game. In the reliability extension, each agent only "survives" with a certain probability, and a coalition's value is the probability that its surviving members would be a winning coalition in the base game. We study prominent solution concepts in such games, showing how to approximate the Shapley value and how to compute the core in games with few agent types. We also show that applying the reliability extension may stabilize the game, making the core non-empty even when the base game has an empty core.

Details

TIST Journal 2010 Journal Article

Structured coalitions in resource selection games

  • Michal Feldman
  • Moshe Tennenholtz

We study stability against coalitional deviations in resource selection games where the coalitions have a certain structure. In particular, the agents are partitioned into coalitions, and only deviations by the prescribed coalitions are considered. This is in contrast to the classical concept of strong equilibrium according to which any subset of the agents may deviate. In resource selection games, each agent selects a resource from a set of resources, and its payoff is an increasing (or nondecreasing) function of the number of agents selecting its resource. While it has been shown that a strong equilibrium always exists in resource selection games, a closer look reveals severe limitations to the applicability of the existence result even in the simplest case of two identical resources with increasing cost functions. First, these games do not possess a super strong equilibrium in which a fruitful deviation benefits at least one deviator without hurting any other deviator. Second, a strong equilibrium may not exist when the game is played repeatedly. We prove that for any given partition, there exists a super strong equilibrium for resource selection games of identical resources with increasing cost functions. In addition, we show similar existence results for a variety of other classes of resource selection games. For the case of repeated games, we characterize partitions that guarantee the existence of a strong equilibrium. Together, our work introduces a natural concept, which turns out to lead to positive and applicable results in one of the basic domains studied in the literature.

Details DOI