BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Ioannis Caragiannis

Ioannis Caragiannis contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryData Structures and AlgorithmsComputational ComplexityMultiagent SystemsArtificial IntelligenceDiscrete MathematicsSocial and Information Networksecon.THMachine Learningmath.PR

Trust snapshot

Quick read

Trust 21 - Emerging
27works
0followers
10topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Almost Envy-Free Allocations with Connected Bundles

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Impartial Selection with Additive Approximation Guarantees

Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a community by other members, to select the member with the highest number of nominations. This seemingly trivial goal becomes challenging when there is an additional impartiality constraint, requiring that no single member can influence her chance of being selected. Recent progress has identified impartial selection rules with optimal approximation ratios. Moreover, it was noted that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of the quality of impartial selection. Our positive results include two randomized impartial selection mechanisms which have additive approximation guarantees of $Θ(\sqrt{n})$ and $Θ(n^{2/3}\ln^{1/3}n)$ for the two most studied models in the literature, where $n$ denotes the community size. We complement our positive results by providing negative results for various cases. First, we provide a characterization for the interesting class of strong sample mechanisms, which allows us to obtain lower bounds of $n-2$, and of $Ω(\sqrt{n})$ for their deterministic and randomized variants respectively. Finally, we present a general lower bound of $2$ for all deterministic impartial mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimizing over Serial Dictatorships

Motivated by the success of the serial dictatorship mechanism in social choice settings, we explore its usefulness in tackling various combinatorial optimization problems. We do so by considering an abstract model, in which a set of agents are asked to act in a particular ordering, called the action sequence. Each agent acts in a way that gives her the maximum possible value, given the actions of the agents who preceded her in the action sequence. Our goal is to compute action sequences that yield approximately optimal total value to the agents (a.k.a., social welfare). We assume query access to the value $v_i(S)$ that the agent i gets when she acts after the agents in the ordered set $S$. We establish tight bounds on the social welfare that can be achieved using polynomially many queries. Even though these bounds show a marginally sublinear approximation of optimal social welfare in general, excellent approximations can be obtained when the valuations stem from an underlying combinatorial domain. Indicatively, when the valuations are defined using bipartite matchings, arborescences in directed graphs, and satisfiability of Boolean expressions, simple query-efficient algorithms yield $2$-approximations. We discuss issues related to truthfulness and show how some of our algorithms can be implemented truthfully using VCG-like payments. Finally, we introduce and study the price of serial dictatorship, a notion that provides an optimistic measure of the quality of combinatorial optimization solutions generated by action sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Repeatedly Matching Items to Agents Fairly and Efficiently

We consider a novel setting where a set of items are matched to the same set of agents repeatedly over multiple rounds. Each agent gets exactly one item per round, which brings interesting challenges to finding efficient and/or fair {\em repeated matchings}. A particular feature of our model is that the value of an agent for an item in some round depends on the number of rounds in which the item has been used by the agent in the past. We present a set of positive and negative results about the efficiency and fairness of repeated matchings. For example, when items are goods, a variation of the well-studied fairness notion of envy-freeness up to one good (EF1) can be satisfied under certain conditions. Furthermore, it is intractable to achieve fairness and (approximate) efficiency simultaneously, even though they are achievable separately. For mixed items, which can be goods for some agents and chores for others, we propose and study a new notion of fairness that we call {\em swap envy-freeness} (swapEF).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Metric Distortion of Multiwinner Voting

We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, $n$ agents and $m$ alternatives are located in an underlying metric space. The exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of $k$ alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the $q$-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of $k$ and $q$: The distortion is unbounded when $q \leq k/3$, asymptotically linear in the number of agents when $k/3 < q \leq k/2$, and constant when $q > k/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Truthful Aggregation of Budget Proposals with Proportionality Guarantees

We study a participatory budgeting problem, where a set of strategic agents wish to split a divisible budget among different projects, by aggregating their proposals on a single division. Unfortunately, the straight-forward rule that divides the budget proportionally is susceptible to manipulation. In a recent work, Freeman et al. [arXiv:1905.00457] proposed a class of truthful mechanisms, called moving phantom mechanisms. Among others, they propose a proportional mechanism, in the sense that in the extreme case where all agents prefer a single project to receive the whole amount, the budget is assigned proportionally. While proportionality is a naturally desired property, it is defined over a limited type of preference profiles. To address this, we expand the notion of proportionality, by proposing a quantitative framework which evaluates a budget aggregation mechanism according to its worst-case distance from the proportional allocation. Crucially, this is defined for every preference profile. We study this measure on the class of moving phantom mechanisms, and we provide approximation guarantees. For two projects, we show that the Uniform Phantom mechanism is the optimal among all truthful mechanisms. For three projects, we propose a new, proportional mechanism which is virtually optimal among all moving phantom mechanisms. Finally, we provide impossibility results regarding the approximability of moving phantom mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Computing envy-freeable allocations with limited subsidies

Fair division has emerged as a very hot topic in multiagent systems, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are {\em envy-freeable} using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm that, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a super-constant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Impartial selection with prior information

We study the problem of {\em impartial selection}, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular individual among a set of community members. The input can be modeled as a directed graph, where each node represents an individual, and a directed edge indicates nomination or approval of a community member to another. An {\em impartial mechanism} is robust to potential selfish behavior of the individuals and provides appropriate incentives to voters to report their true preferences by ensuring that the chance of a node to become a winner does not depend on its outgoing edges. The goal is to design impartial mechanisms that select a node with an in-degree that is as close as possible to the highest in-degree. We measure the efficiency of such a mechanism by the difference of these in-degrees, known as its {\em additive} approximation. In particular, we study the extent to which prior information on voters&#39; preferences could be useful in the design of efficient deterministic impartial selection mechanisms with good additive approximation guarantees. We consider three models of prior information, which we call the {\em opinion poll}, the {\em a prior popularity}, and the {\em uniform} model. We analyze the performance of a natural selection mechanism that we call {\em approval voting with default} (AVD) and show that it achieves a $O(\sqrt{n\ln{n}})$ additive guarantee for opinion poll and a $O(\ln^2n)$ for a priori popularity inputs, where $n$ is the number of individuals. We consider this polylogarithmic bound as our main technical contribution. We complement this last result by showing that our analysis is close to tight, showing an $Ω(\ln{n})$ lower bound. This holds in the uniform model, which is the simplest among the three models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

How effective can simple ordinal peer grading be?

Ordinal peer grading has been proposed as a simple and scalable solution for computing reliable information about student performance in massive open online courses. The idea is to outsource the grading task to the students themselves as follows. After the end of an exam, each student is asked to rank -- in terms of quality -- a bundle of exam papers by fellow students. An aggregation rule then combines the individual rankings into a global one that contains all students. We define a broad class of simple aggregation rules, which we call type-ordering aggregation rules, and present a theoretical framework for assessing their effectiveness. When statistical information about the grading behaviour of students is available (in terms of a noise matrix that characterizes the grading behaviour of the average student from a student population), the framework can be used to compute the optimal rule from this class with respect to a series of performance objectives that compare the ranking returned by the aggregation rule to the underlying ground truth ranking. For example, a natural rule known as Borda is proved to be optimal when students grade correctly. In addition, we present extensive simulations that validate our theory and prove it to be extremely accurate in predicting the performance of aggregation rules even when only rough information about grading behaviour (i.e., an approximation of the noise matrix) is available. Both in the application of our theoretical framework and in our simulations, we exploit data about grading behaviour of students that have been extracted from two field experiments in the University of Patras.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The efficiency of resource allocation mechanisms for budget-constrained users

We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis [Mathematics of Operations Research, 2004], a long list of papers studied the price of anarchy (in terms of the social welfare --- the total users&#39; value) of resource allocation mechanisms for a variety of allocation and payment rules. Here, we further assume that each user has a budget constraint that invalidates strategies that yield a payment that is higher than the user&#39;s budget. This subtle assumption, which is arguably more realistic, constitutes the traditional price of anarchy analysis meaningless as the set of equilibria may change drastically and their social welfare can be arbitrarily far from optimal. Instead, we study the price of anarchy using the liquid welfare benchmark that measures efficiency taking budget constraints into account. We show a tight bound of 2 on the liquid price of anarchy of the well-known Kelly mechanism and prove that this result is essentially best possible among all multi-user resource allocation mechanisms. This comes in sharp contrast to the no-budget setting where there are mechanisms that considerably outperform Kelly in terms of social welfare and even achieve full efficiency. In our proofs, we exploit the particular structure of worst-case games and equilibria, which also allows us to design (nearly) optimal two-player mechanisms by solving simple differential equations.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Truthful ownership transfer with expert advice: Blending mechanism design with and without money

When a company undergoes a merger or transfers its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, like the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the opinions of the internal experts. Motivated by such scenarios, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in {\em hybrid social choice} settings, where payments can be imposed to the bidders, but not to the experts. Since this problem is a combination of mechanism design with and without monetary transfers, classical solutions like VCG cannot be applied, making this a novel mechanism design problem. We consider the simple but fundamental scenario with one expert and two bidders, and provide tight approximation guarantees of the optimal social welfare. We distinguish between mechanisms that use ordinal and cardinal information, as well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several non-trivial randomized truthful mechanisms, and also allows for closer-to-optimal welfare guarantees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Algorithmic Framework for Strategic Fair Division

We study the paradigmatic fair division problem of allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classical cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, by designing a concrete computational framework for fair division---the class of Generalized Cut and Choose (GCC) protocols}---and reasoning about the game-theoretic properties of algorithms that operate in this model. The class of GCC protocols includes the most important discrete cake cutting protocols, and turns out to be compatible with the study of fair division among strategic agents. In particular, GCC protocols are guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol&#39;s tie-breaking rule is flexible. We further observe that the (approximate) equilibria of proportional GCC protocols---which guarantee each of the $n$ agents a $1/n$-fraction of the cake---must be (approximately) proportional. Finally, we design a protocol in this framework with the property that its Nash equilibrium allocations coincide with the set of (contiguous) envy-free allocations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An almost ideal coordination mechanism for unrelated machine scheduling

Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism \Dcoord) that is superior to all known mechanisms. \Dcoord\ induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Discrete Preference Games in Heterogeneous Social Networks: Subverted Majorities and the Swing Player

We study discrete preference games in heterogeneous social networks. These games model the interplay between a player&#39;s private belief and his/her publicly stated opinion (which could be different from the player&#39;s belief) as a strategic game in which the players&#39; strategies are the opinions and the cost of an opinion in a state is a convex combination through a parameter $α\in[0,1]$ of two factors: the disagreement between the player&#39;s opinion and his/her internal belief and the number of neighbors whose opinions differ from the one of the player. The parameter $α$ models how stubborn a player is: players with large $α$ change their opinion only if many neighbors disagree with his/her belief. We consider social networks that are heterogeneous in the sense that the parameter $α$ can vary from player to player. We ask if it is possible that the belief shared by the majority of the players does not coincide with the opinion that is publicly announced by the majority of the players in an equilibrium state. Our main result is a characterization of the social networks that admit an initial belief assignment for which there exists a sequence of best response moves that reach an equilibrium in which the initial majority is subverted. Our characterization is effective in the sense that can be tested efficiently and the initial belief assignment that can be subverted can be computed in time polynomial in the number of players. Our result is actually stronger as we show that in each initial belief assignment that can be subverted, subversion is actually obtained in a very strong way: it only takes one move of a single player, the swing player, to lead the social network to a point of no return in which any rational move from any player leads to a subverted majority.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Opting Into Optimal Matchings

We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player --- who is associated with a subset of vertices --- matches as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result asserts that, under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points. We propose a resource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a very well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Although Serial Dictatorship is a purely combinatorial mechanism, our analysis uses linear programming; a linear program expresses its greedy nature as well as the structure of the input, and finds the input instance that enforces the mechanism have its worst-case performance. Bounding the objective of the linear program using duality arguments allows us to compute tight bounds on the approximation ratio. Among other results, we prove that Serial Dictatorship has approximation ratio $g/(g-2)$ when the capacities are multiplied by any integer $g \geq 3$. Our results suggest that even a limited augmentation of the resources can have wondrous effects on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minority Becomes Majority in Social Networks

It is often observed that agents tend to imitate the behavior of their neighbors in a social network. This imitating behavior might lead to the strategic decision of adopting a public behavior that differs from what the agent believes is the right one and this can subvert the behavior of the population as a whole. In this paper, we consider the case in which agents express preferences over two alternatives and model social pressure with the majority dynamics: at each step an agent is selected and its preference is replaced by the majority of the preferences of her neighbors. In case of a tie, the agent does not change her current preference. A profile of the agents&#39; preferences is stable if the preference of each agent coincides with the preference of at least half of the neighbors (thus, the system is in equilibrium). We ask whether there are network topologies that are robust to social pressure. That is, we ask if there are graphs in which the majority of preferences in an initial profile always coincides with the majority of the preference in all stable profiles reachable from that profile. We completely characterize the graphs with this robustness property by showing that this is possible only if the graph has no edge or is a clique or very close to a clique. In other words, except for this handful of graphs, every graph admits at least one initial profile of preferences in which the majority dynamics can subvert the initial majority. We also show that deciding whether a graph admits a minority that becomes majority is NP-hard when the minority size is at most 1/4-th of the social network size.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near-optimal asymmetric binary matrix partitions

We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (WINE 2013) to model the impact of asymmetric information on the revenue of the seller in take-it-or-leave-it sales. Instances of the problem consist of an $n \times m$ binary matrix $A$ and a probability distribution over its columns. A partition scheme $B=(B_1,...,B_n)$ consists of a partition $B_i$ for each row $i$ of $A$. The partition $B_i$ acts as a smoothing operator on row $i$ that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme $B$ that induces a smooth matrix $A^B$, the partition value is the expected maximum column entry of $A^B$. The objective is to find a partition scheme such that the resulting partition value is maximized. We present a $9/10$-approximation algorithm for the case where the probability distribution is uniform and a $(1-1/e)$-approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Aggregating partial rankings with applications to peer grading in massive online open courses

We investigate the potential of using ordinal peer grading for the evaluation of students in massive online open courses (MOOCs). According to such grading schemes, each student receives a few assignments (by other students) which she has to rank. Then, a global ranking (possibly translated into numerical scores) is produced by combining the individual ones. This is a novel application area for social choice concepts and methods where the important problem to be solved is as follows: how should the assignments be distributed so that the collected individual rankings can be easily merged into a global one that is as close as possible to the ranking that represents the relative performance of the students in the assignment? Our main theoretical result suggests that using very simple ways to distribute the assignments so that each student has to rank only $k$ of them, a Borda-like aggregation method can recover a $1-O(1/k)$ fraction of the true ranking when each student correctly ranks the assignments she receives. Experimental results strengthen our analysis further and also demonstrate that the same method is extremely robust even when students have imperfect capabilities as graders. We believe that our results provide strong evidence that ordinal peer grading can be a highly effective and scalable solution for evaluation in MOOCs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounding the inefficiency of outcomes in generalized second price auctions

The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this auction and that inefficient equilibria can arise. In this paper we study the space of equilibria in GSP, and quantify the efficiency loss that can arise in equilibria under a wide range of sources of uncertainty, as well as in the full information setting. The traditional Bayesian game models uncertainty in the valuations (types) of the participants. The Generalized Second Price (GSP) auction gives rise to a further form of uncertainty: the selection of quality factors resulting in uncertainty about the behavior of the underlying ad allocation algorithm. The bounds we obtain apply to both forms of uncertainty, and are robust in the sense that they apply under various perturbations of the solution concept, extending to models with information asymmetries and bounded rationality in the form of learning strategies. We present a constant bound (2.927) on the factor of the efficiency loss (\emph{price of anarchy}) of the corresponding game for the Bayesian model of partial information about other participants and about ad quality factors. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria, nearly matching a lower bound of 1.259 for the case of three advertisers. Further, we do not require that the system reaches equilibrium, and give similarly low bounds also on the quality degradation for any no-regret learning outcome. Our conclusion is that the number of advertisers in the auction has almost no impact on the price of anarchy, and that the efficiency of GSP is very robust with respect to the belief and rationality assumptions imposed on the participants.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games

We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al.~(EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property which, to the best of our knowledge, was not known before. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Welfare guarantees for proportional allocations

According to the proportional allocation mechanism from the network optimization literature, users compete for a divisible resource -- such as bandwidth -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of 26.8% on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to 50% over both equilibrium concepts. Our analysis is simpler and, furthermore, we argue that it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between 36% and 50%) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of (pure Nash) equilibria is guaranteed by potential function arguments. Unfortunately, this proof of existence is inefficient and computing equilibria is such games is a {\sf PLS}-hard problem. The situation gets worse when superlinear latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and equilibria may not even exist. Given these obstacles, we consider approximate equilibria as alternative solution concepts. Do such equilibria exist? And if so, can we compute them efficiently? We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an &#34;approximation&#34; of such games by a new class of potential games that we call $Ψ$-games. This allows us to show that these games have $d!$-approximate equilibria, where $d$ is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate equilibria when $d$ is a constant. For games with linear latency functions, the approximation guarantee is $\frac{3+\sqrt{5}}{2}+O(γ)$ for arbitrarily small $γ>0$; for latency functions with maximum degree $d\geq 2$, it is $d^{2d+o(d)}$. The running time is polynomial in the number of bits in the representation of the game and $1/γ$. As a byproduct of our techniques, we also show the following structural statement for weighted congestion games with polynomial latency functions of maximum degree $d\geq 2$: polynomially-long sequences of best-response moves from any initial state to a $d^{O(d^2)}$-approximate equilibrium exist and can be efficiently identified in such games as long as $d$ is constant.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient computation of approximate pure Nash equilibria in congestion games

Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general {\sf PLS}-complete. We present a surprisingly simple polynomial-time algorithm that computes O(1)-approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes $(2+ε)$-approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and $1/ε$. It also applies to games with polynomial latency functions with constant maximum degree $d$; there, the approximation guarantee is $d^{O(d)}$. The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium; the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing $ρ$-approximate equilibria is {\sf PLS}-complete for any polynomial-time computable $ρ$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient coordination mechanisms for unrelated machine scheduling

We present new coordination mechanisms for scheduling selfish jobs on $m$ unrelated machines. A coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game. Our mechanisms are deterministic, local, and preemptive. Our first coordination mechanism has approximation ratio $Θ(\log m)$ and guarantees that the induced game has pure Nash equilibria. This result improves a bound of $O(\log^2 m)$ due to Azar, Jain, and Mirrokni and uses a global ordering of the jobs according to their distinct IDs. Our second mechanism handles anonymous jobs and has approximation ratio $O(\frac{\log m}{\log \log m})$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice cost-revealing potential function. We use this potential function in order to prove the existence of equilibria and to upper-bound the price of anarchy of the induced game by $O(\log^2m)$. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Enforcing efficient equilibria in network design games via subsidies

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users&#39; selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results.

0 citations0 reviewsNo code linkedOpen access