View in EDS HTML Full Text PDF Full Text

Optimizing Over Serial Dictatorships.

Saved in:
Bibliographic Details
Title: Optimizing Over Serial Dictatorships.
Authors: Caragiannis, Ioannis1 (AUTHOR) iannis@cs.au.dk, Rathi, Nidhi2 (AUTHOR)
Source: Theory of Computing Systems. Oct2024, Vol. 68 Issue 5, p1180-1206. 27p.
Subjects: Boolean expressions, Combinatorial optimization, Social services, Social choice, Prices
Abstract: 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. [ABSTRACT FROM AUTHOR]
Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 180500454
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Optimizing Over Serial Dictatorships.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Caragiannis%2C+Ioannis%22">Caragiannis, Ioannis</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> iannis@cs.au.dk</i><br /><searchLink fieldCode="AR" term="%22Rathi%2C+Nidhi%22">Rathi, Nidhi</searchLink><relatesTo>2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Oct2024, Vol. 68 Issue 5, p1180-1206. 27p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Boolean+expressions%22">Boolean expressions</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Social+services%22">Social services</searchLink><br /><searchLink fieldCode="DE" term="%22Social+choice%22">Social choice</searchLink><br /><searchLink fieldCode="DE" term="%22Prices%22">Prices</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=180500454
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-024-10196-6
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 27
        StartPage: 1180
    Subjects:
      – SubjectFull: Boolean expressions
        Type: general
      – SubjectFull: Combinatorial optimization
        Type: general
      – SubjectFull: Social services
        Type: general
      – SubjectFull: Social choice
        Type: general
      – SubjectFull: Prices
        Type: general
    Titles:
      – TitleFull: Optimizing Over Serial Dictatorships.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Caragiannis, Ioannis
      – PersonEntity:
          Name:
            NameFull: Rathi, Nidhi
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2024
              Type: published
              Y: 2024
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 68
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1