Contact Sitemap Search Login Webmail Magyar
The main website of the Hungarian Academy of Sciences
Research Institutes of the Hungarian Academy of Sciences

Workshop on Computational Social Choice


Description | Participants | ProgramVenue | What is COMSOC? |Pictures

Preliminary program

9:00-9:30 Arrival, registration

9:30-10:30 1st session, chair: Katarína Cechlárová

  1. Péter Biró: Computational and strategic issues in the Hungarian higher education matching scheme
  2. Francesca Rossi: Weights in stable marriage problems increase manipulation opportunities
  3. Tamás Fleiner: On stable matchings and flows

10:30-11:00 coffee break

11:00-12:00 2nd session, chair: Ulle Endriss

  1. Christian Klamler: A geometric approach to judgement aggregation
  2. Markus Brill: Necessary and Sufficient Conditions for the Strategyproofness of Irresolute Social Choice Functions
  3. Daniel Eckert: Decisiveness structures in judgment aggregation

12:00-13:00 lunch break (in house)

13:00-14:00 3rd session, chair: Francesca Rossi

  1. Britta Dorn: A multivariate complexity analysis of Swap Bribery
  2. László Á. Kóczy: Power indices when players can commit to quarrel
  3. Robert Bredereck: On Making a Distinguished Vertex Minimum Degree by Vertex Deletion: How Resistant is Control by Removing Candidates for the Llull Voting Rule

14:00-14:30 coffee break

14:30-15:30 4th session, chair: Tamás Fleiner

  1. Katarína Cechlárová: On the existence and computability of equitable cake divisions
  2. Pietro Speroni di Fenizio and Cyril Velikanov: Fair participation: special case of fair division, or something else?
  3. Ioannis Caragiannis: On the efficiency of equilibria in generalized second price auctions

15:30-16:00 coffee break

16:00-17:00 5th session, chair: László Kóczy

  1. Ulle Endriss: The Agenda Choice Problem in Multi-Issue Elections
  2. Attila Tasnádi: Computational aspects of the political districting problem
  3. Balázs Sziklai: Mechanics in Game Theory: Fair Division Rules

Dinner

From 18:00 in Jardinette restaurant

Abstracts

Péter Biró: Computational and strategic issues in the Hungarian higher education matching scheme

Student admissions, for both secondary schools and higher education, are organised by centralised matching schemes in Hungary. The secondary school program is based precisely on the original model and algorithm of Gale and Shapley. The core of the algorithm is the same for the higher education scheme, but the related model has at least four special features that are interesting to study in a theoretical sense as well.

This is a joint work with Tamás Fleiner, Rob Irving and David Manlove.

Robert Bredereck: On Making a Distinguished Vertex Minimum Degree by Vertex Deletion: How Resistant is Control by Removing Candidates for the Llull Voting Rule

We analyze the parameterized complexity of electoral control by removing candidates for the Llull voting rule (Copeland with full score for ties). Here one asks whether a chair can make a distinguished candidate become a winner by removing a bounded number of candidates. We show that the problem is W[2]-hard when parameterized by the underlying graph's feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters "feedback vertex set number" and "number of candidates to delete". This means that resistance to this control scenario in form of computational intractability "even holds" when the instances are "almost acyclic". In contrast, one can efficiently decide whether removing only few candidates from "less cyclic" instances suffice to make the distinguished candidate become a winner. More precisely, for constant parameter values the problem is polynomial-time solvable and the degree of the polynomial does not depend on the parameters.

Markus Brill: Necessary and Sufficient Conditions for the Strategyproofness of Irresolute Social Choice Function

While the Gibbard-Satterthwaite theorem states that every non-dictatorial and resolute, i.e., single-valued, social choice function is manipulable, it was recently shown that a number of appealing irresolute Condorcet extensions are strategyproof according to Kelly’s preference extension. In this paper, we study whether these results carry over to stronger preference extensions due to Fishburn and Gärdenfors. For both preference extensions, we provide sufficient conditions for strategyproofness and identify social choice functions that satisfy these conditions, answering a question by Gärdenfors (1976) in the affirmative. We also show that some more discriminatory social choice functions fail to satisfy necessary conditions for strategyproofness.

Ioannis Caragiannis: On the efficiency of equilibria in generalized second price auctions

In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically and submit their bids in order to maximize their individual objectives, such an auction naturally defines a strategic game among the advertisers. The efficiency of outcomes in such auctions can be quantified using the notion of the price of anarchy of the corresponding games. In this talk, we will consider the strategic games induced by generalized second price auctions which are widely used by the sponsored search industry. We will present recent results on the price of anarchy of such games over pure Nash and coarse correlated equilibria in the full information setting as well as over Bayes-Nash equilibria in the incomplete information setting.

The talk is based on joint work with Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou (ACM EC11, to appear).

Katarína Cechlárová: On the existence and computability of equitable cake divisions

Let the cake be represented by the unit interval and let each player have a valuation expressed by a nonatomic probability measure. We are interested in divisions that give each player a contiguous cake piece (simple divisions). A cake division is said to be equitable if the value of the piece assigned to a player by her measure is the same for all players. We show that for any number n of players an equitable simple division exists. Moreover, there is always an order of players in which an equitable simple division is also proportional.

On the other hand, we show that there is no finite algorithm to compute the cutpoints of such divisions already for n = 3. Hence we propose an algorithm that finds in a finite number of steps a proportional simple division in which the values of players’ pieces differ by at most a given small positive constant.

This talk reports on the results obtained in collaboration with Jozef Doboš and Eva Pillárová.

Britta Dorn: A multivariate complexity analysis of Swap Bribery

We consider the computational complexity of a problem modeling bribery in the context of voting systems. In the scenario of Swap Bribery, each voter assigns a certain price for swapping the positions of two consecutive candidates in his preference ranking. The question is whether it is possible, without exceeding a given budget, to bribe the voters in a way that the preferred candidate wins in the election.  We focus on the case of k-approval and analyze the Swap Bribery problem from a multivariate complexity point of view, providing further insight into how the complexity of the problem depends on different parameters such as the cost function, the budget, the number of candidates, or the number of votes.The presented results are joint work with Ildi Schlotter.

Daniel Eckert: Decisiveness structures in judgment aggregation

The set theoretic analysis of the collections of winning coalitions has proven useful for deriving and understanding impossibility results in preference aggregation. We show its use in the more general case of judgment aggregation.

Ulle Endriss: The Agenda Choice Problem in Multi-Issue Election

Conducting a multi-issue election is challenging: On the one hand, requiring voters to express their preferences over all combinations of issues is computationally infeasible; on the other, decomposing the problem into several elections on smaller sets of issues can lead to paradoxical outcomes. Any pragmatic method for  running a multi-issue election will have to balance these two concerns. In this talk I will introduce and discuss the agenda choice problem: the problem of choosing an agenda for a given election, determining which issues to vote on together in local elections and in which order to schedule those local elections. This is joint work with Stéphane Airiau, Umberto Grandi, Daniele Porello and Joel Uckelman.

Tamás Fleiner: On stable matchings and flows

We describe a flow model that generalizes ordinary network flows the same way as stable matchings generalize the bipartite matching problem. We prove that there always exists a stable flow and generalize the lattice structure of stable marriages to stable flows. Our main tool is a straightforward reduction of the stable flow problem to stable allocations.

Christian Klamler: A geometric approach to judgement aggregation

Judgement aggregation investigates the aggregation of individual judgements on logically interrelated propositions into a set of consistent group judgements. For a simple 3 propositions setting, we will apply a geometric approach in the spirit of Don Saari to derive and analyse certain (impossibility) results.

László Á. Kóczy: Power indices when players can commit to quarrel

A power index measures the statistical probability of a voter being instrumental in a voting situation. Despite the fact that they are studied as part of game theory, there is nothing “game theoretical,” strategic about them. The fairness represented by values seems less fit to measure power. Current indices seem to measure voting luck. Power is the “ability to act or produce an effect.” Strategic decisions that increase a voter's ability to make decisions are a manifestation of power. What are the strategic decisions a voter can take? Quarrelling players (Kilgour, T&D 1977) refuse to cooperate, two such players refuse to join the same coalition so a coalition may contain at most one quarrelling player. In fact, two players may mutually benefit from their quarrelling. In this paper we allow for similar strategic decisions, except that 1) quarrelling can be unilateral, it does not require the agreement of all parties and 2) quarrelling does not extend to subsets of the quarrelling coalition. Should all winning coalitions form? Property rights, the structure of communication, or physical or ideological position may have put some exogenous restrictions on the set of feasible coalitions. Would all coalitions form in the absence of such restrictions. When a player is offered to join a winning coalition, accepting will clearly cause no harm. A priori, however, she may benefit from a commitment to refuse to join this coalition. But even ex post a voter may turn down membership in a coalition where she gets no, or too little credit for membership expecting more from the average winning coalition. Our model formalises this possibility: we augment voting games with a previous stage, where players can choose the coalitions they want to join in the voting game. This is a simple noncooperative game, where “the acquisition of power is the payoff” (Shapley, Behav. Sci., 1962, p. 59). We show that the known normalised indices are affected by such strategic behaviour.

Francesca Rossi: Weights in stable marriage problems increase manipulation opportunities

Joint work with Maria Silvia Pini, Kristen Brent Venable, Toby Walsh.The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications,  ranging from matching resident doctors to hospitals, to matching students to schools or more generally to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here we consider stable marriage problems with weighted preferences, where each man (resp., woman) provides a score for each woman (resp., man), and we define new stability notions for such problems. In this context, we consider the manipulability properties of the procedures that return stable marriages. While we know that all procedures are manipulable by modifying the preference lists or by truncating them, here we consider if manipulation can occur also by just modifying the weights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, we indeed increase the possibility of manipulating and this cannot be avoided by any reasonable restriction on the weights.

Pietro Speroni di Fenizio and Cyril Velikanov: Fair participation: special case of fair division, or something else?

It is common in collaborative systems to allow users to submit their contributions (proposals and/or comments) and then evaluate each other's contributions. Most of such systems also exhibit a list of the highest rated contributions, with an implicit assumption that those are the best, the most relevant, the most interesting ones. Indeed, the highest rated ones are often interesting enough, but the opposite is not necessarily true. With a system as described above (of a kind that is nearly ubiquitous on the Internet), a really good contribution may easily pass unnoticed, without ever being evaluated at its real importance and real interest it presents. In a sense, this issue, which we call “fair collaboration” or “fair participation”, is related to a well-known research topic, “fair division”. We will analyze how the two topics are relating to each other, and under what assumption can "fair collaboration" be seen as a case of “fair division”. We will also suggest some possible solutions, and draft directions of further study.

Balázs Sziklai: Mechanics in Game Theory: Fair Division Rules

Proof techniques that use the principles of mechanics were very common in the ancient times. The increasing number of examples in the literature shows that they are no less useful today. Here we focus on division rules and their physical representation. Our work is based on Kaminski's idea. In 2000 he introduced a new concept to model the bankruptcy game and other rationing problems: the hydraulic rationing. This method can be used to give a simple proof to the well-known theorem of Aumann and Mashler i.e. the consistent solution of a bankruptcy problem is the nucleolus of the corresponding game. We use a system of vessels and water and the principles of mechanics to show this fact. Joint work with Tamás Fleiner.

Attila Tasnádi: Computational aspects of the political districting problem

Following a brief comparison of the computational and social choice literature on the political districting problem, we show that determining an optimal districting for a party, an unbiased districting and a status quo preserving redistricting are NP-complete problems. We consider various settings and possible geographies. In addition, we comment on the so called pack and crack principle.

The Institute's
networking infrastructure
is provided by NIIF.
MTA - Magyar Tudományos Akadémia HAS
Hungarian Academy of Sciences
 
Page last modified: 18 October, 2013