Optimal Bundle Selection in Combinatorial Voting

This work explores optimal bundle selection in combinatorial voting scenarios, focusing on satisfying user preferences and applying Condorcet criteria and related voting rules for effective decision-making.

• Bundle Selection
• Combinatorial Voting
• Condorcet Criteria
• Decision-Making

shubb Follow

Uploaded on Mar 07, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Condorcet Consistent Bundling with Social Choice Shreyas Sekar, Sujoy Sikdar, Lirong Xia

2. Optimal Bundle Selection Journals in a Library Many journals to choose from Limited space ECONOMETRICA J A I R Algorithmica Software ? ? ? Users have preferences over the journals Examples: Committees, TV channel packages, insurance policies,

3. Optimal Bundle Selection: Preferences Software Linear orders on the journals: Motivating Question How to select bundles of size k to satisfy majority of users, who have preferences over individual items? Condorcet Criterion Copeland Maximin/Minimax This Work Ranked Pairs Schulze

4. The Condorcet Criterion Candidate who defeats every other candidate by pair-wise majority, must be the winner. Software Voting rule > > Software > > > Software > Software

5. Relaxing Condorcet: Different notions of winners Copeland: most pairwise victories Condorcet winners may not always exist: how to select? Maximin: maximize the minimum margin of victory

6. Relaxing Condorcet via Tournament Graphs Copeland: most pairwise victories Maximin: maximize the minimum margin of victory 1 2 Depend only on (weighted) tournament graph Tournament graph ? Weighted Tournament graph ? Software 2 2 Copeland: maximum outgoing edges in ? Maximin: maximize the minimum weight of any outgoing edge in ? Other Condorcet Consistent Rules:Ranked Pairs, Schulze,

7. Condorcet criterion for Bundles Combinatorial Voting Care about every item Compare all bundles Proportional Representation Care about favorite item Compare bundle to items outside the bundle [Gehrlein, 1985] Our Work Condorcet Winning Bundle Every item in the bundle, defeats every item outside

8. Another Angle on Gehrleins notion Every item in the bundle, defeats every item outside Strong Gehrlein Stability Defeats every neighboring bundle Local dominance: Compare to neighboring bundles

9. Weighted majority graphs for ?-size bundles Software Software Software Local (Weighted) Majority graph of ?-bundles ?(?) (?(?)) Condorcet criterion: Bundle with outgoing edges to every neighbor Local Condorcet winner [Xia et al. 08, Conitzer et al. 11]

10. Generic Template for Condorcet Consistent Bundling Condorcet winning bundles may not always exist Single winner Condorcet rule depending on ?(?) Bundling Condorcet rule depending on ?(?)(?(?)) Copeland(k) bundle: maximum outgoing edges in ?(?) Maximin (k)bundle: maximizes the minimum weight of any outgoing edge in ?(?)

11. JAIR Example (N=100 users, k=3) Software 35 55 80 Software JAIR Maximin Winning Bundle Software 80 90 JAIR Software (score = 35) 70 JAIR 55 Copeland winning bundle (score = 2 bundles defeated)

12. Copeland(k) Mechanism Copeland winner iff it maximizes pairwise defeats of items not in the bundle Maximum size cut in ? Theorem: Compute optimal Copeland (k) bundle efficiently (no ties case): Select ? items with largest out-degree in ?

13. Maximin(k) Mechanism Computing optimal bundle of size ? is NP-hard Relax size constraint Maximin Score of Bundle B Largest 0 s.t, at least users prefer B to any neighbor B .

14. Size-Relaxing Maximin-Approx. Theorem Compute bundle of size 2? that is as good as Opt.bundle of size k in terms of maximin score Why? Seller may have some flexibility in deciding the size. Cost borne by a benevolent seller, not buyer. Buyers pay for ?, and get a larger bundle that is at least as good as the best bundle of size ?. Example: Government run library, tele-education package,

15. Copeland ? - Dealing with ties ? controls importance of tie ? = 0 R I A J ECONOMETRICA R I A J R I A J ? = 0.5 ECONOMETRICA COMSOC Algorithmica ? = 1 ECONOMETRICA

16. Copeland?(?) Copeland?(?) score is ????????? + ? ???? in ?(?) Winner computation hard for ? = 0,1 OPT for ? = 0.5 using greedy algorithm Pick k items w/ highest score. 0.5-approx. using MAX-DICUT min(2 ,1/2 )-approx. using greedy algorithm

17. Ranked Pairs and Schulze for Bundles ?(?) Sort edges of ? by dec. weight Select edge if it does no cycle Winner has no incoming edges Ranked Pairs(?) ?(?) ??(?,?) min weight of ? ? path in ? ? (?,?) = max ? Winner a : ? ? ,? ? ?,? Schulze(?) ??(?,?) Results Poly-time algorithm for winning Ranked Pairs(?) and Schulze (?) bundles