Vasilis Gkatzelis

Search for another author

Author Description

2021-01-01

Vasilis Gkatzelis , R. Patel , Emmanouil Pountourakis +1 more

View PDF Chat

2016-09-21

Richard Cole , Nikhil R. Devanur , Vasilis Gkatzelis +4 more

Online Nash Social Welfare Maximization with Predictions

2020-01-01

Siddhartha Banerjee , Vasilis Gkatzelis , Artur Gorokh +1 more

We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which … We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of $T$ periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial $O(N)$, unless it is given additional information about the agents' values. Then, in line with the emerging area of "algorithms with predictions", we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the $T$ periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of $O(\log N)$ and $O(\log T)$ if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of $O(\log^{1-\epsilon} N)$ or $O(\log^{1-\epsilon} T)$ for any constant $\epsilon>0$.

View PDF Chat

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-08-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior … We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

View PDF Chat

Best of Both Distortion Worlds

2023-07-07

Vasilis Gkatzelis , Mohamad Latifian , Nisarg Shah

We study the problem of designing voting rules that take as input the ordinal preferences of n agents over a set of n alternatives and output a single alternative, aiming … We study the problem of designing voting rules that take as input the ordinal preferences of n agents over a set of n alternatives and output a single alternative, aiming to optimize the overall happiness of the agents. The input to the voting rule is each agent's ranking of the alternatives from most to least preferred, yet the agents have more refined (cardinal) preferences that capture the intensity with which they prefer one alternative over another. To quantify the extent to which voting rules can optimize over the cardinal preferences given access only to the ordinal ones, prior work has used the distortion measure, i.e., the worst-case approximation ratio between a voting rule's performance and the best performance achievable given the cardinal preferences.

View PDF Chat

Resolving the Optimal Metric Distortion Conjecture

2020-04-16

Vasilis Gkatzelis , Daniel Halpern , Nisarg Shah

We study the following metric distortion problem: there are two finite sets of points, $V$ and $C$, that lie in the same metric space, and our goal is to choose … We study the following metric distortion problem: there are two finite sets of points, $V$ and $C$, that lie in the same metric space, and our goal is to choose a point in $C$ whose total distance from the points in $V$ is as small as possible. However, rather than having access to the underlying distance metric, we only know, for each point in $V$, a ranking of its distances to the points in $C$. We propose algorithms that choose a point in $C$ using only these rankings as input and we provide bounds on their \emph{distortion} (worst-case approximation ratio). A prominent motivation for this problem comes from voting theory, where $V$ represents a set of voters, $C$ represents a set of candidates, and the rankings correspond to ordinal preferences of the voters. A major conjecture in this framework is that the optimal deterministic algorithm has distortion $3$. We resolve this conjecture by providing a polynomial-time algorithm that achieves distortion $3$, matching a known lower bound. We do so by proving a novel lemma about matching voters to candidates, which we refer to as the \emph{ranking-matching lemma}. This lemma induces a family of novel algorithms, which may be of independent interest, and we show that a special algorithm in this family achieves distortion $3$. We also provide more refined, parameterized, bounds using the notion of $\alpha$-decisiveness, which quantifies the extent to which a voter may prefer her top choice relative to all others. Finally, we introduce a new randomized algorithm with improved distortion compared to known results, and also provide improved lower bounds on the distortion of all deterministic and randomized algorithms.

Resource-Aware Protocols for Network Cost-Sharing Games

2020-07-09

George Christodoulou , Vasilis Gkatzelis , Mohamad Latifian +1 more

We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with $n$ agents. We focus on the model of … We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with $n$ agents. We focus on the model of resource-aware protocols, where the designer has prior access to the network structure and can also increase the total cost of an edge(overcharging), and we study classes of games with concave or convex cost functions. We first consider concave cost functions and our main result is a cost-sharing protocol for symmetric games on directed acyclic graphs that achieves a PoA of $2+\varepsilon$ for some arbitrary small positive $\varepsilon$, which improves to $1+\varepsilon$ for games with at least two players. We also achieve a PoA of 1 for series-parallel graphs and show that no protocol can achieve a PoA better than $\Omega(\sqrt{n})$ for multicast games. We then also consider convex cost functions and prove analogous results for series-parallel networks and multicast games, as well as a lower bound of $\Omega(n)$ for the PoA on directed acyclic graphs without the use of overcharging.

View PDF Chat

Online Nash Social Welfare via Promised Utilities.

2020-08-08

Artur Gorokh , Siddhartha Banerjee , Billy Jin +1 more

We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner over $T$ periods, with adversarially-chosen normalized valuations in each period. Our goal … We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner over $T$ periods, with adversarially-chosen normalized valuations in each period. Our goal is to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. On the positive side, we provide an online algorithm that achieves a competitive ratio of $O(\log N)$ and $O(\log T)$, but also a stronger competitive ratio of $O(\log k)$ in settings where the value of any agent for her most preferred item is no more than $k$ times her average value. We complement this by showing this bound is essentially tight: no online algorithm can achieve a competitive ratio of $O(\log^{1-\epsilon} N)$ or $O(\log^{1-\epsilon} T)$ for any constant $\epsilon>0$.

Nash Social Welfare Approximation for Strategic Agents

2016-07-06

Simina Brânzei , Vasilis Gkatzelis , Ruta Mehta

The fair division of resources is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether … The fair division of resources is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist fair mechanisms despite strategic behavior of the agents. A fundamental objective function used for measuring fair outcomes is the Nash social welfare, defined as the geometric mean of the agent utilities. This objective function is maximized by widely known solution concepts such as Nash bargaining and the competitive equilibrium with equal incomes. In this work we focus on the question of (approximately) implementing the Nash social welfare. The starting point of our analysis is the Fisher market, a fundamental model of an economy, whose benchmark is precisely the (weighted) Nash social welfare. We begin by studying two extreme classes of valuations functions, namely perfect substitutes and perfect complements, and find that for perfect substitutes, the Fisher market mechanism has a constant approximation: at most 2 and at least e1e. However, for perfect complements, the Fisher market does not work well, its bound degrading linearly with the number of players. Strikingly, the Trading Post mechanism---an indirect market mechanism also known as the Shapley-Shubik game---has significantly better performance than the Fisher market on its own benchmark. Not only does Trading Post achieve an approximation of 2 for perfect substitutes, but this bound holds for all concave utilities and becomes arbitrarily close to optimal for Leontief utilities (perfect complements), where it reaches $(1+\epsilon)$ for every $\epsilon > 0$. Moreover, all the Nash equilibria of the Trading Post mechanism are pure for all concave utilities and satisfy an important notion of fairness known as proportionality.

Prior-Free Clock Auctions for Bidders with Interdependent Values

2021-07-20

Vasilis Gkatzelis , R. Patel , Emmanouil Pountourakis +1 more

We study the problem of selling a good to a group of bidders with interdependent values in a prior-free setting. Each bidder has a signal that can take one of … We study the problem of selling a good to a group of bidders with interdependent values in a prior-free setting. Each bidder has a signal that can take one of $k$ different values, and her value for the good is a weakly increasing function of all the bidders' signals. The bidders are partitioned into $\ell$ expertise-groups, based on how their signal can impact the values for the good, and we prove upper and lower bounds regarding the approximability of social welfare and revenue for a variety of settings, parameterized by $k$ and $\ell$. Our lower bounds apply to all ex-post incentive compatible mechanisms and our upper bounds are all within a small constant of the lower bounds. Our main results take the appealing form of ascending clock auctions and provide strong incentives by admitting the desired outcomes as obvious ex-post equilibria.

Bayesian and Randomized Clock Auctions

2022-07-12

Michal Feldman , Vasilis Gkatzelis , Nick Gravin +1 more

In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving … In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving this service, and some feasibility constraint restricts which subsets of buyers can be served simultaneously. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and very strong incentive guarantees. Subsequent work in computer science focused on evaluating these auctions with respect to their social welfare approximation guarantees, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets.

View PDF Chat

Strategyproof Scheduling with Predictions

2022-01-01

Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan

In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the … In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the makespan. They provided a strategyproof mechanism that achieves an $n$-approximation and they made the bold conjecture that this is the best approximation achievable by any deterministic strategyproof scheduling mechanism. After more than two decades and several efforts, $n$ remains the best known approximation and very recent work by \citet{CKK21} has been able to prove an $\Omega(\sqrt{n})$ approximation lower bound for all deterministic strategyproof mechanisms. This strong negative result, however, heavily depends on the fact that the performance of these mechanisms is evaluated using worst-case analysis. To overcome such overly pessimistic, and often uninformative, worst-case bounds, a surge of recent work has focused on the ``learning-augmented framework'', whose goal is to leverage machine-learned predictions to obtain improved approximations when these predictions are accurate (consistency), while also achieving near-optimal worst-case approximations even when the predictions are arbitrarily wrong (robustness). In this work, we study the classic strategic scheduling problem of~\citet{NR99} using the learning-augmented framework and give a deterministic polynomial-time strategyproof mechanism that is $6$-consistent and $2n$-robust. We thus achieve the ``best of both worlds'': an $O(1)$ consistency and an $O(n)$ robustness that asymptotically matches the best-known approximation. We then extend this result to provide more general worst-case approximation guarantees as a function of the prediction error. Finally, we complement our positive results by showing that any $1$-consistent deterministic strategyproof mechanism has unbounded robustness.

View PDF Chat

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2023-12-27

Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more

In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to … In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are inaccurate (robustness). We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well, even when the predictions are not fully accurate. Funding: The work of E. Balkanski was supported in part by the National Science Foundation [Grants CCF-2210501 and IIS-2147361]. The work of V. Gkatzelis and X. Tan was supported in part by the National Science Foundation [Grant CCF-2210502] and [CAREER Award CCF-2047907].

View PDF Chat

Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division

2024-07-26

Vasilis Gkatzelis , Alexandros Psomas , Xizhi Tan +1 more

We study fair resource allocation with strategic agents. It is well-known that, across multiple fundamental problems in this domain, truthfulness and fairness are incompatible. For example, when allocating indivisible goods, … We study fair resource allocation with strategic agents. It is well-known that, across multiple fundamental problems in this domain, truthfulness and fairness are incompatible. For example, when allocating indivisible goods, no truthful and deterministic mechanism can guarantee envy-freeness up to one item (EF1), even for two agents with additive valuations. Or, in cake-cutting, no truthful and deterministic mechanism always outputs a proportional allocation, even for two agents with piecewise constant valuations. Our work stems from the observation that, in the context of fair division, truthfulness is used as a synonym for Dominant Strategy Incentive Compatibility (DSIC), requiring that an agent prefers reporting the truth, no matter what other agents report. In this paper, we instead focus on Bayesian Incentive Compatible (BIC) mechanisms, requiring that agents are better off reporting the truth in expectation over other agents' reports. We prove that, when agents know a bit less about each other, a lot more is possible: using BIC mechanisms we can achieve fairness notions that are unattainable by DSIC mechanisms in both the fundamental problems of allocation of indivisible goods and cake-cutting. We prove that this is the case even for an arbitrary number of agents, as long as the agents' priors about each others' types satisfy a neutrality condition. Notably, for the case of indivisible goods, we significantly strengthen the state-of-the-art negative result for efficient DSIC mechanisms, while also highlighting the limitations of BIC mechanisms, by showing that a very general class of welfare objectives is incompatible with Bayesian Incentive Compatibility. Combined, these results give a near-complete picture of the power and limitations of BIC and DSIC mechanisms for the problem of allocating indivisible goods.

View PDF Chat

Mechanism Design with Predictions: An Annotated Reading List

2023-06-01

Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan

A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are … A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are accurate. This "learning-augmented" framework was recently also extended to mechanism design settings involving strategic agents and we provide an overview of these results.

Truthfulness, Proportional Fairness, and Efficiency

2012-03-20

Richard Cole , Vasilis Gkatzelis , Gagan Goel

How does one allocate a collection of resources to a set of strategic agents in a fair and efficient manner without using money? For in many scenarios it is not … How does one allocate a collection of resources to a set of strategic agents in a fair and efficient manner without using money? For in many scenarios it is not feasible to use money to compensate agents for otherwise unsatisfactory outcomes. This paper studies this question, looking at both fairness and efficiency measures. We employ the proportionally fair solution, which is a well-known fairness concept for money-free settings. But although finding a proportionally fair solution is computationally tractable, it cannot be implemented in a truthful fashion. Consequently, we seek approximate solutions. We give several truthful mechanisms which achieve proportional fairness in an approximate sense. We use a strong notion of approximation, requiring the mechanism to give each agent a good approximation of its proportionally fair utility. In particular, one of our mechanisms provides a better and better approximation factor as the minimum demand for every good increases. A motivating example is provided by the massive privatization auction in the Czech republic in the early 90s. With regard to efficiency, prior work has shown a lower bound of 0.5 on the approximation factor of any swap-dictatorial mechanism approximating a social welfare measure even for the two agents and multiple goods case. We surpass this lower bound by designing a non-swap-dictatorial mechanism for this case. Interestingly, the new mechanism builds on the notion of proportional fairness.

Truthful Mechanisms for Proportionally Fair Allocations

2012-03-20

Richard Cole , Vasilis Gkatzelis , Gagan Goel

We study the problem of designing mechanisms to allocate a heterogeneous set of divisible goods among a set of agents in a fair manner. We consider the well known solution … We study the problem of designing mechanisms to allocate a heterogeneous set of divisible goods among a set of agents in a fair manner. We consider the well known solution concept of proportional fairness that has found applications in many real-world scenarios. Although finding a proportionally fair solution is computationally tractable, it cannot be implemented in a truthful manner. To overcome this, in this paper, we give mechanisms which are truthful and achieve proportional fairness in an approximate manner. We use a strong notion of approximation, requiring the mechanism to give each agent a good approximation of its proportionally fair utility. A motivating example is provided by the massive privatization auction in the Czech republic in the early 90s.

Inner Product Spaces for MinSum Coordination Mechanisms

2010-10-10

Richard Cole , José R. Correa , Vasilis Gkatzelis +2 more

We study policies aiming to minimize the weighted sum of completion times of jobs in the context of coordination mechanisms for selfish scheduling problems. Our goal is to design local … We study policies aiming to minimize the weighted sum of completion times of jobs in the context of coordination mechanisms for selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain the approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. With this method we are able to prove the following results. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed. We prove that ProportionalSharing, a preemptive strongly local policy, achieves an approximation ratio of 2.618 for the weighted sum of completion times, and an approximation ratio of 2.5 in the unweighted case. Again, we observe that these bounds are tight. Next, we consider Rand, a natural non-preemptive but randomized policy. We show that it achieves an approximation ratio of at most 2.13; moreover, if the sum of the weighted completion times is negligible compared to the cost of the optimal solution, this improves to \pi /2. Finally, we show that both ProportionalSharing and Rand induce potential games, and thus always have a pure Nash equilibrium (unlike Smith's Rule). This also allows us to design the first \emph{combinatorial} constant-factor approximation algorithm minimizing weighted completion time for unrelated machine scheduling that achieves a factor of 2+ \epsilon for any \epsilon > 0.

Fair and Efficient Online Allocations with Normalized Valuations

2020-01-01

Vasilis Gkatzelis , Alexandros Psomas , Xizhi Tan

A set of divisible resources becomes available over a sequence of rounds and needs to be allocated immediately and irrevocably. Our goal is to distribute these resources to maximize fairness … A set of divisible resources becomes available over a sequence of rounds and needs to be allocated immediately and irrevocably. Our goal is to distribute these resources to maximize fairness and efficiency. Achieving any non-trivial guarantees in an adversarial setting is impossible. However, we show that normalizing the agent values, a very common assumption in fair division, allows us to escape this impossibility. Our main result is an online algorithm for the case of two agents that ensures the outcome is envy-free while guaranteeing 91.6% of the optimal social welfare. We also show that this is near-optimal: there is no envy-free algorithm that guarantees more than 93.3% of the optimal social welfare.

View PDF Chat

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-05-24

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Resource-Aware Cost-Sharing Mechanisms with Priors

2021-06-03

Vasilis Gkatzelis , Emmanouil Pountourakis , Alkmini Sgouritsa

In a decentralized system with $m$ machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a … In a decentralized system with $m$ machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games. Recent work introduced the class of \emph{resource-aware} cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families. In this paper we show that if we enhance the class of resource-aware mechanisms with some prior information regarding the users, then they can achieve low PoA for a much more general family of cost functions. We first show that, as long as the mechanism knows just two of the participating users, then it can assign special roles to them and ensure a constant PoA. We then extend this idea to settings where the mechanism has access to the probability with which each user is present in the system. For all these instances, we provide a mechanism that achieves an expected PoA that is logarithmic in the expected number of users.

Achieving Proportionality up to the Maximin Item with Indivisible Goods.

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Resource-Aware Cost-Sharing Mechanisms with Priors

2021-07-18

Vasilis Gkatzelis , Emmanouil Pountourakis , Alkmini Sgouritsa

In a decentralized system with m machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a … In a decentralized system with m machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games. Recent work introduced the class of resource-aware cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families.

View PDF Chat

Deterministic Budget-Feasible Clock Auctions

2021-01-01

Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

2022-01-01

Ioannis Caragiannis , Vasilis Gkatzelis , Alexandros Psomas +1 more

The problem of fair division known as "cake cutting" has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been … The problem of fair division known as "cake cutting" has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the "cake" but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.

View PDF Chat

Bayesian and Randomized Clock Auctions

2022-01-01

Michal Feldman , Vasilis Gkatzelis , Nick Gravin +1 more

In a single-parameter mechanism design problem, a provider is looking to sell a service to a group of potential buyers. Each buyer $i$ has a private value $v_i$ for receiving … In a single-parameter mechanism design problem, a provider is looking to sell a service to a group of potential buyers. Each buyer $i$ has a private value $v_i$ for receiving the service and a feasibility constraint restricts which sets of buyers can be served simultaneously. Recent work in economics introduced clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and strong incentive guarantees. Subsequent work focused on evaluating the social welfare approximation guarantees of these auctions, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets. We show that these negative results can be circumvented by using prior information or by leveraging randomization. We provide clock auctions that give a $O(\log\log k)$ approximation for general downward-closed feasibility constraints with $k$ maximal feasible sets for three different information models, ranging from full access to the value distributions to complete absence of information. The more information the seller has, the simpler these auctions are. Under full access, we use a particularly simple deterministic clock auction, called a single-price clock auction, which is only slightly more complex than posted price mechanisms. In this auction, each buyer is offered a single price and a feasible set is selected among those who accept their offers. In the other extreme, where no prior information is available, this approximation guarantee is obtained using a complex randomized clock auction. In addition to our main results, we propose a parameterization that interpolates between single-price clock auctions and general clock auctions, paving the way for an exciting line of future research.

View PDF Chat

Prior-Free Clock Auctions for Bidders with Interdependent Values

2021-01-01

Vasilis Gkatzelis , R. Patel , Emmanouil Pountourakis +1 more

View PDF Chat

Resource-Aware Cost-Sharing Mechanisms with Priors

2021-01-01

Vasilis Gkatzelis , Emmanouil Pountourakis , Alkmini Sgouritsa

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-01-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2020-01-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

View PDF Chat

Optimal Metric Distortion for Matching on the Line

2025-01-31

Aris Filos-Ratsikas , Vasilis Gkatzelis , Mohamad Latifian +2 more

We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, $n$ agents need to be matched to $n$ items, and each agent's cost … We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, $n$ agents need to be matched to $n$ items, and each agent's cost in a matching is their distance from the item they were matched to. We propose an algorithm that is provided only with ordinal information regarding the agents' preferences (each agent's ranking of the items from most- to least-preferred) and returns a matching aiming to minimize the social cost with respect to the agents' true (cardinal) costs. We prove that our algorithm simultaneously achieves the best-possible approximation of $3$ (known as distortion) with respect to a variety of social cost measures which include the utilitarian and egalitarian social cost. In the two-sided case, where the agents need be matched to $n$ other agents and both sides report their ordinal preferences over each other, we show that it is always possible to compute an optimal matching. In fact, we show that this optimal matching can be achieved using even less information, and we provide bounds regarding the sufficient number of queries.

View PDF Chat

2023-07-07

Vasilis Gkatzelis , Mohamad Latifian , Nisarg Shah

View PDF Chat

Mechanism Design with Predictions: An Annotated Reading List

2023-06-01

Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan

Optimal Data Acquisition with Privacy-Aware Agents

2023-02-01

Rachel Cummings , Hadi Elzayn , Emmanouil Pountourakis +2 more

View PDF Chat

2023-01-01

Ben Berger , Michal Feldman , Vasilis Gkatzelis +1 more

In the metric distortion problem there is a set of candidates and a set of voters, all residing in the same metric space. The objective is to choose a candidate … In the metric distortion problem there is a set of candidates and a set of voters, all residing in the same metric space. The objective is to choose a candidate with minimum social cost, defined as the total distance of the chosen candidate from all voters. The challenge is that the algorithm receives only ordinal input from each voter, in the form of a ranked list of candidates in non-decreasing order of their distances from her, whereas the objective function is cardinal. The distortion of an algorithm is its worst-case approximation factor with respect to the optimal social cost. A series of papers culminated in a 3-distortion algorithm, which is tight with respect to all deterministic algorithms. Aiming to overcome the limitations of worst-case analysis, we revisit the metric distortion problem through the learning-augmented framework, where the algorithm is provided with some prediction regarding the optimal candidate. The quality of this prediction is unknown, and the goal is to evaluate the performance of the algorithm under a accurate prediction (known as consistency), while simultaneously providing worst-case guarantees even for arbitrarily inaccurate predictions (known as robustness). For our main result, we characterize the robustness-consistency Pareto frontier for the metric distortion problem. We first identify an inevitable trade-off between robustness and consistency. We then devise a family of learning-augmented algorithms that achieves any desired robustness-consistency pair on this Pareto frontier. Furthermore, we provide a more refined analysis of the distortion bounds as a function of the prediction error (with consistency and robustness being two extremes). Finally, we also prove distortion bounds that integrate the notion of $\alpha$-decisiveness, which quantifies the extent to which a voter prefers her favorite candidate relative to the rest.

Online Mechanism Design with Predictions

2023-01-01

2022-01-01

Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more

In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to … In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design. We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate.

View PDF Chat

Proportionally Fair Online Allocation of Public Goods with Predictions

2022-01-01

Siddhartha Banerjee , Vasilis Gkatzelis , Safwan Hossain +3 more

We design online algorithms for the fair allocation of public goods to a set of $N$ agents over a sequence of $T$ rounds and focus on improving their performance using … We design online algorithms for the fair allocation of public goods to a set of $N$ agents over a sequence of $T$ rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, the algorithm learns every agent's value for the good, and must irrevocably decide the amount of investment in the good without exceeding a total budget of $B$ across all rounds. The algorithm can utilize (potentially inaccurate) predictions of each agent's total value for all the goods to arrive. We measure the performance of the algorithm using a proportional fairness objective, which informally demands that every group of agents be rewarded in proportion to its size and the cohesiveness of its preferences. In the special case of binary agent preferences and a unit budget, we show that $O(\log N)$ proportional fairness can be achieved without using any predictions, and that this is optimal even if perfectly accurate predictions were available. However, for general preferences and budget no algorithm can achieve better than $\Theta(T/B)$ proportional fairness without predictions. We show that algorithms with (reasonably accurate) predictions can do much better, achieving $\Theta(\log (T/B))$ proportional fairness. We also extend this result to a general model in which a batch of $L$ public goods arrive in each round and achieve $O(\log (\min(N,L) \cdot T/B))$ proportional fairness. Our exact bounds are parametrized as a function of the error in the predictions and the performance degrades gracefully with increasing errors.

View PDF Chat

Improved Price of Anarchy via Predictions

2022-01-01

Vasilis Gkatzelis , Kostas Kollias , Alkmini Sgouritsa +1 more

A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can … A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can enforce how these systems are utilized, the users can strategically interact with the system, aiming to maximize their own utility, possibly leading to very inefficient outcomes, and thus a high price of anarchy. To alleviate this issue, the system designer can use decentralized mechanisms that regulate the use of each resource (e.g., using local queuing protocols or scheduling mechanisms), but with only limited information regarding the state of the system. These information limitations have a severe impact on what such decentralized mechanisms can achieve, so most of the success stories in this literature have had to make restrictive assumptions (e.g., by either restricting the structure of the networks or the types of cost functions). In this paper, we overcome some of the obstacles that the literature has imposed on decentralized mechanisms, by designing mechanisms that are enhanced with predictions regarding the missing information. Specifically, inspired by the big success of the literature on "algorithms with predictions", we design decentralized mechanisms with predictions and evaluate their price of anarchy as a function of the prediction error, focusing on two very well-studied classes of games: scheduling games and multicast network formation games.

View PDF Chat

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-08-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

View PDF Chat

2021-01-01

Vasilis Gkatzelis , Emmanouil Pountourakis , Alkmini Sgouritsa

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-01-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Resolving the Optimal Metric Distortion Conjecture

2020-11-01

Vasilis Gkatzelis , Daniel Halpern , Nisarg Shah

View PDF Chat

Online Nash Social Welfare via Promised Utilities.

2020-08-08

Artur Gorokh , Siddhartha Banerjee , Billy Jin +1 more

Resource-Aware Protocols for Network Cost-Sharing Games

2020-07-09

George Christodoulou , Vasilis Gkatzelis , Mohamad Latifian +1 more

View PDF Chat

Coauthor	Papers Together
Xizhi Tan	21
Daniel Schoepflin	16
Richard Cole	14
Eric Balkanski	10
Pranav Garimidi	8
Emmanouil Pountourakis	8
Nisarg Shah	7
Alkmini Sgouritsa	7
Artem Baklanov	6
Gagan Goel	6
Siddhartha Banerjee	5
Billy Jin	5
Alexandros Psomas	5
Simina Brânzei	4
Mohamad Latifian	4
Ruta Mehta	4
Michal Feldman	4
Neil Olver	3
Artur Gorokh	3
R. Patel	3
Vijay V. Vazirani	3
Priyank Agrawal	3
Tingting Ou	3
Sadra Yazdanbod	3
José R. Correa	3
Kamal Jain	3
Vahab Mirrokni	3
Tung Mai	3
Nikhil R. Devanur	3
Jason D. Hartline	2
Hadi Elzayn	2
Juba Ziani	2
Nick Gravin	2
Paritosh Verma	2
Kostas Kollias	2
Marius Garbea	2
Evi Micha	2
Ke Yang	2
Rediet Abebe	2
Daniel Halpern	2
Rachel Cummings	2
Ben Berger	2
Julia Stoyanovich	2
Safwan Hossain	2
Cherlin Zhu	2
Emma Rewinski	1
Daniel Halpern	1
Aris Filos-Ratsikas	1
George Christodoulou	1
Ioannis Caragiannis	1

Consensus of Subjective Probabilities: The Pari-Mutuel Method

1959-03-01

E. Eisenberg , David Gale

Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted … Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted by the amounts of their bets. The properties which this consensus must possess and prove that there always exists a unique set of odds having the required properties are formulated. (Author)

View PDF Chat

Nash Social Welfare Approximation for Strategic Agents

2017-06-20

Simina Brânzei , Vasilis Gkatzelis , Ruta Mehta

View PDF Chat

Finding Fair and Efficient Allocations

2018-06-11

Siddharth Barman , Sanath Kumar Krishnamurthy , Rohit Vaish

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if … We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto efficiency. While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare objective is both EF1 and Pareto efficient. However, the problem of maximizing Nash social welfare is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and Pareto efficient; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally Pareto efficient. Another key contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the Nash social welfare objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al., 2017), and also matches the lower bound on the integrality gap of the convex program of Cole et al. (2017). Unlike many of the existing approaches, our algorithm is completely combinatorial, and relies on constructing integral Fisher markets wherein specific equilibria are not only efficient, but also fair.

View PDF Chat

Truthful fair division

2010-10-18

Elchanan Mossel , Omer Tamuz

APX-hardness of maximizing Nash social welfare with indivisible items

2017-02-23

Euiwoong Lee

View PDF Chat

Fairness-Efficiency Tradeoffs in Dynamic Fair Division

2020-07-09

David Zeng , Alexandros Psomas

A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a way that is fair and efficient. A standard fairness … A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a way that is fair and efficient. A standard fairness concept is envy-freeness, which requires that each agent prefers her own allocation over the allocation of any other agent. Even though envy is clearly unavoidable in this context - consider the case of a single indivisible good and two agents - providing approximately envy-free solutions is possible [3, 6]. Specifically, an allocation is envy-free up to one item (EF1) if for every pair of agents i and j, any envy i has for j can be eliminated by removing at most one good from j's bundle. Recently, Caragiannis et al. [3] show that the allocation that maximizes the product of the agents' utilities (with ties broken based on the number of agents with positive utility) is EF1 and Pareto efficient. The majority of the literature to date has focused on the case where the items are available to the algorithm upfront. In many situations of interest, however, items arrive online. A paradigmatic example is that of food banks [1, 5]. Food banks across the world receive food donations they must allocate; these donations are often perishable, and thus allocation decisions must be made quickly, and donations are typically leftovers, leading to uncertainty about items that will arrive in the future. Benadè et al. [2] study this problem, but focus only on fairness. They show that there exists a deterministic algorithm with vanishing envy, that is, the maximum pairwise envy (after all T items have been allocated) is sublinear in T , when the value vit of agent i for the t-th item is normalized to be in [0, 1]. Specifically, the envy is guaranteed to be at most O(√p T logT /n), and this guarantee is tight up to polylogarithmic factors. The same guarantee can also be achieved by the simple randomized algorithm that allocates each item to a uniformly random agent. These results hold even against an adaptive adversary that selects the value vit after seeing the allocation of the first t - 1 items. On the other hand, if we focus only on efficiency, our task is much easier. For example, we could simply allocate each item to the agent with the highest value. But, and this brings us to our interest here, the question remains: How should we make allocation decisions online in a way that is fair to the donation recipients, but also as efficient as possible?

View PDF Chat

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

2013-02-14

George Christodoulou , Kurt Mehlhorn , Evangelia Pyrga

View PDF Chat

Convex Program Duality, Fisher Markets, and Nash Social Welfare

2017-06-20

Richard Cole , Nikhil R. Devanur , Vasilis Gkatzelis +4 more

No abstract available. No abstract available.

2012-01-01

Avishay Maya , Noam Nisan

View PDF Chat

A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

2020-07-09

Haris Aziz , Hervé Moulin , Fedor Sandomirskiy

View PDF Chat

Mechanism design for fair division

2013-06-16

Richard Cole , Vasilis Gkatzelis , Gagan Goel

View PDF Chat

2012-04-24

Ioannis Caragiannis

View PDF Chat

Improved Metric Distortion for Deterministic Social Choice Rules

2019-06-17

Kamesh Munagala , Kangning Wang

In this paper, we study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. Voters and candidates … In this paper, we study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. Voters and candidates are located in an underlying metric space. A voter has cost equal to her distance to the winning candidate. Ordinal social choice rules only have access to the ordinal preferences of the voters that are assumed to be consistent with the metric distances. Our goal is to design an ordinal social choice rule with minimum distortion, which is the worst-case ratio, over all consistent metrics, between the social cost of the rule and that of the optimal omniscient rule with knowledge of the underlying metric space. The distortion of the best deterministic social choice rule was known to be between 3 and 5. It had been conjectured that any rule that only looks at the weighted tournament graph on the candidates cannot have distortion better than 5. In our paper, we disprove it by presenting a weighted tournament rule with distortion of 4.236. We design this rule by generalizing the classic notion of uncovered sets, and further show that this class of rules cannot have distortion better than 4.236. We then propose a new voting rule, via an alternative generalization of uncovered sets. We show that if a candidate satisfying the criterion of this voting rule exists, then choosing such a candidate yields a distortion bound of 3, matching the lower bound. We present a combinatorial conjecture that implies distortion of $3$, and verify it for small numbers of candidates and voters by computer experiments. Using our framework, we also show that selecting any candidate guarantees distortion of at most 3 when the weighted tournament graph is cyclically symmetric.

View PDF Chat

Communication, Distortion, and Randomness in Metric Voting

2020-04-03

David Kempe

In distortion-based analysis of social choice rules over metric spaces, voters and candidates are jointly embedded in a metric space. Voters rank candidates by non-decreasing distance. The mechanism, receiving only … In distortion-based analysis of social choice rules over metric spaces, voters and candidates are jointly embedded in a metric space. Voters rank candidates by non-decreasing distance. The mechanism, receiving only this ordinal (comparison) information, must select a candidate approximately minimizing the sum of distances from all voters to the chosen candidate. It is known that while the Copeland rule and related rules guarantee distortion at most 5, the distortion of many other standard voting rules, such as Plurality, Veto, or k-approval, grows unboundedly in the number n of candidates.An advantage of Plurality, Veto, or k-approval with small k is that they require less communication from the voters; all deterministic social choice rules known to achieve constant distortion require voters to transmit their complete rankings of all candidates. This motivates our study of the tradeoff between the distortion and the amount of communication in deterministic social choice rules.We show that any one-round deterministic voting mechanism in which each voter communicates only the candidates she ranks in a given set of k positions must have distortion at least 2n-k/k; we give a mechanism achieving an upper bound of O(n/k), which matches the lower bound up to a constant. For more general communication-bounded voting mechanisms, in which each voter communicates b bits of information about her ranking, we show a slightly weaker lower bound of Ω(n/b) on the distortion.For randomized mechanisms, Random Dictatorship achieves expected distortion strictly smaller than 3, almost matching a lower bound of 3 − 2/n for any randomized mechanism that only receives each voter's top choice. We close this gap, by giving a simple randomized social choice rule which only uses each voter's first choice, and achieves expected distortion 3 − 2/n.

1983-05-01

Man-Duen Choi

Click to increase image sizeClick to decrease image size Additional informationNotes on contributorsMan-Duen ChoiMan-Duen Choi was brought up in Hong Kong. He received his Ph.D. degree under the guidance of … Click to increase image sizeClick to decrease image size Additional informationNotes on contributorsMan-Duen ChoiMan-Duen Choi was brought up in Hong Kong. He received his Ph.D. degree under the guidance of Chandler Davis at Toronto. He taught at the University of California, Berkeley, from 1973 to 1976, and has worked since then at the University of Toronto. His research has been mainly in operator algebras, operator theory, and polynomial rings. He is particularly interested in examples/counterexamples and two-by-two matrix manipulations.

Dynamic Weighted Fairness with Minimal Disruptions

2020-06-08

Sungjin Im , Benjamin Moseley , Kamesh Munagala +1 more

In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the … In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work.

View PDF Chat

Approximately stable committee selection

2020-06-22

Zhihao Jiang , Kamesh Munagala , Kangning Wang

In the committee selection problem, we are given m candidates, and n voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the … In the committee selection problem, we are given m candidates, and n voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over all possible committees. The only assumption we make on preferences is monotonicity: If S ⊆ S′ are two committees, then any voter weakly prefers S′ to S.

View PDF Chat

Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games

2014-05-27

Ragavendran Gopalakrishnan , Jason R. Marden , Adam Wierman

We consider the problem of designing distribution rules to share “welfare” (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a … We consider the problem of designing distribution rules to share “welfare” (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a (pure) Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantees the existence of a Nash equilibrium is unknown. Our work provides an exact characterization of this space for a specific class of scalable and separable games that includes a variety of applications such as facility location, routing, network formation, and coverage games. Given arbitrary local welfare functions 𝕨, we prove that a distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is equivalent to a generalized weighted Shapley value on some “ground” welfare functions 𝕨′, which can be distinct from 𝕨. However, if budget-balance is required in addition to the existence of a Nash equilibrium, then 𝕨′ must be the same as 𝕨. We also provide an alternate characterization of this space in terms of “generalized” marginal contributions, which is more appealing from the point of view of computational tractability. A possibly surprising consequence of our result is that, in order to guarantee equilibrium existence in all games with any fixed local welfare functions, it is necessary to work within the class of potential games.

View PDF Chat

A Simple and Approximately Optimal Mechanism for an Additive Buyer

2020-06-16

Moshe Babaioff , Nicole Immorlica , Brendan Lucier +1 more

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value … We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately , each at its optimal price, and bundling together , in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

View PDF Chat

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

View PDF Chat

The linear exchange model

1976-07-01

David Gale

Ranking with Fairness Constraints

2018-01-01

L. Elisa Celis , Damian Straszak , Nisheeth K. Vishnoi

Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown that, left unchecked, … Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown that, left unchecked, the output of ranking algorithms can result in decreased diversity in the type of content presented, promote stereotypes, and polarize opinions. In order to address such issues, we study the following variant of the traditional ranking problem when, in addition, there are fairness or diversity constraints. Given a collection of items along with 1) the value of placing an item in a particular position in the ranking, 2) the collection of sensitive attributes (such as gender, race, political opinion) of each item and 3) a collection of fairness constraints that, for each k, bound the number of items with each attribute that are allowed to appear in the top k positions of the ranking, the goal is to output a ranking that maximizes the value with respect to the original rank quality metric while respecting the constraints. This problem encapsulates various well-studied problems related to bipartite and hypergraph matching as special cases and turns out to be hard to approximate even with simple constraints. Our main technical contributions are fast exact and approximation algorithms along with complementary hardness results that, together, come close to settling the approximability of this constrained ranking maximization problem. Unlike prior work on the approximability of constrained matching problems, our algorithm runs in linear time, even when the number of constraints is (polynomially) large, its approximation ratio does not depend on the number of constraints, and it produces solutions with small constraint violations. Our results rely on insights about the constrained matching problem when the objective function satisfies certain properties that appear in common ranking metrics such as discounted cumulative gain (DCG), Spearman's rho or Bradley-Terry, along with the nested structure of fairness constraints.

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs

2019-11-01

Vincent Cohen-Addad , Michał Pilipczuk , Marcin Pilipczuk

We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C ⊆ V(G), a set of facilities F … We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C ⊆ V(G), a set of facilities F ⊆ V(G), and opening costs open: F → R ≥0 , the goal is to find a subset D of F that minimizes Σ cϵC min fϵD dist(c,f) + Σ fϵD open(f). The Facility Location problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any ε>0, computes a solution of cost at most (1+ε) times the optimum in time n (2 O(ε(-2) log(1/ε)) ) .

View PDF Chat

2011-01-06

Johanne Cohen , Christoph Dürr , Nguyễn Kim Thắng

In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost … In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy -- the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.

Almost envy-freeness with general valuations

2018-01-07

Benjamin Plaut , Tim Roughgarden

The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always … The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the division of indivisible goods with different classes of player valuations.

Randomized Social Choice Functions Under Metric Preferences

2017-04-13

Elliot Anshelevich , John Postl

We determine the quality of randomized social choice algorithms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs … We determine the quality of randomized social choice algorithms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the algorithms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between the expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized algorithms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic algorithms.

View PDF Chat

An Analysis Framework for Metric Voting based on LP Duality

2020-04-03

David Kempe

Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit … Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by non-decreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule's choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule's distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee distortion at most 5; a very recent result gave a rule with distortion 2 + √5 ≈ 4.236.We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we show that the Ranked Pairs and Schulze rules have distortion Θ(√n). Second, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent 2 + √5 guarantee. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.

View PDF Chat

Strategyproof Facility Location for Concave Cost Functions

2015-07-13

Dimitris Fotakis , Christos Tzamos

View PDF Chat

FA*IR

2017-11-06

Meike Zehlike , Francesco Bonchi , Carlos Castillo +3 more

In this work, we define and solve the Fair Top-k Ranking problem, in which we want to determine a subset of k candidates from a large pool of n >> … In this work, we define and solve the Fair Top-k Ranking problem, in which we want to determine a subset of k candidates from a large pool of n >> k candidates, maximizing utility (i.e., select the "best" candidates) subject to group fairness criteria. Our ranked group fairness definition extends group fairness using the standard notion of protected groups and is based on ensuring that the proportion of protected candidates in every prefix of the top-k ranking remains statistically above or indistinguishable from a given minimum. Utility is operationalized in two ways: (i) every candidate included in the top-$k$ should be more qualified than every candidate not included; and (ii) for every pair of candidates in the top-k, the more qualified candidate should be ranked above. An efficient algorithm is presented for producing the Fair Top-k Ranking, and tested experimentally on existing datasets as well as new datasets released with this paper, showing that our approach yields small distortions with respect to rankings that maximize utility without considering fairness criteria. To the best of our knowledge, this is the first algorithm grounded in statistical tests that can mitigate biases in the representation of an under-represented group along a ranked list.

View PDF Chat

Large Market Games with Near Optimal Efficiency

2016-07-21

Richard Cole , Yixin Tao

As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at particular … As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at particular prices, or in other words, that they are price-takers. An important question is how much the equilibria degrade in the face of strategic behavior, i.e. what is the Price of Anarchy (PoA) of the market viewed as a mechanism?

View PDF Chat

Measuring Fairness in Ranked Outputs

2017-06-05

Ke Yang , Julia Stoyanovich

Ranking and scoring are ubiquitous. We consider the setting in which an institution, called a ranker, evaluates a set of individuals based on demographic, behavioral or other characteristics. The final … Ranking and scoring are ubiquitous. We consider the setting in which an institution, called a ranker, evaluates a set of individuals based on demographic, behavioral or other characteristics. The final output is a ranking that represents the relative quality of the individuals. While automatic and therefore seemingly objective, rankers can, and often do, discriminate against individuals and systematically disadvantage members of protected groups. This warrants a careful study of the fairness of a ranking scheme, to enable data science for social good applications, among others.

View PDF Chat