One way of evaluating social choice (voting) rules is through a utilitarian
distortion framework. In this model, we assume that agents submit full rankings
over the alternatives, and these rankings are generated from underlying, but
unknown, quantitative costs. The \emph{distortion} of a social choice rule is
then the ratio of the total social cost of the chosen alternative to the
optimal social cost of any alternative; since the true costs are unknown, we
consider the worst-case distortion over all possible underlying costs.
Analogously, we can consider the worst-case \emph{fairness ratio} of a social
choice rule by comparing a useful notion of fairness (based on approximate
majorization) for the chosen alternative to that of the optimal alternative.
With an additional metric assumption -- that the costs equal the
agent-alternative distances in some metric space -- it is known that the
Copeland rule achieves both a distortion and fairness ratio of at most 5. For
other rules, only bounds on the distortion are known, e.g., the...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8741

Unqiue Words: 1822

We formalize an allocation model under ordinal preferences that is more
general than the well-studied Shapley-Scarf housing market. In our model, the
agents do not just care which house or resource they get but also care about
who gets their own resource. This assumption is especially important when
considering temporary exchanges in which each resource is eventually returned
to the owner. We show that several positive axiomatic and computational results
that hold for housing markets do not extend to the more general setting. We
then identify natural restrictions on the preferences of agents for which
several positive results do hold. One of our central results is a general class
of algorithms that return any allocation that is individually rational and
Pareto optimal with respect to the responsive set extension.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 5809

Unqiue Words: 1241

We investigate the dependence of steady-state properties of Schelling's
segregation model on the agents' activation order. Our basic formalism is the
Pollicott-Weiss version of Schelling's segregation model. Our main result
modifies this baseline scenario by incorporating contagion in the decision to
move: (pairs of) agents are connected by a second, agent influence network.
Pair activation is specified by a random walk on this network.
The considered schedulers choose the next pair nonadaptively. We can
complement this result by an example of adaptive scheduler (even one that is
quite fair) that is able to preclude maximal segregation. Thus scheduler
nonadaptiveness seems to be required for the validity of the original result
under arbitrary asynchronous scheduling. The analysis (and our result) are part
of an adversarial scheduling approach we are advocating to evolutionary games
and social simulations.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 5461

Unqiue Words: 1694

Direct democracy is a special case of an ensemble of classifiers, where every
person (classifier) votes on every issue. This fails when the average voter
competence (classifier accuracy) falls below 50%, which can happen in noisy
settings where voters have only limited information, or when there are multiple
topics and the average voter competence may not be high enough for some topics.
Representative democracy, where voters choose representatives to vote, can be
an elixir in both these situations. Representative democracy is a specific way
to improve the ensemble of classifiers. We introduce a mathematical model for
studying representative democracy, in particular understanding the parameters
of a representative democracy that gives maximum decision making capability.
Our main result states that under general and natural conditions,
1. Representative democracy can make the correct decisions simultaneously for
multiple noisy issues.
2. When the cost of voting is fixed, the optimal representative democracy
requires that...

more |
pdf
| html
None.

k1ito:
#質問箱一個につき論文一個紹介する
https://t.co/mwJhyEdJ3j
間接民主主義を機械学習的・数理モデル的に解析する論文。
考え・解析は面白いけど別に使い道もなさそうなので深くは読んでないのですが、誰か教えて下さいという意味で紹介。

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 12539

Unqiue Words: 2628

We study the allocation of divisible goods to competing agents via a market
mechanism, focusing on agents with Leontief utilities. The majority of the
economics and mechanism design literature has focused on \emph{linear} prices,
meaning that the cost of a good is proportional to the quantity purchased.
Equilibria for linear prices are known to be exactly the maximum Nash welfare
allocations.
\emph{Price curves} allow the cost of a good to be any (increasing) function
of the quantity purchased. We show that price curve equilibria are not limited
to maximum Nash welfare allocations with two main results. First, we show that
an allocation can be supported by strictly increasing price curves if and only
if it is \emph{group-domination-free}. A similarly characterization holds for
weakly increasing price curves. We use this to show that given any allocation,
we can compute strictly (or weakly) increasing price curves that support it (or
show that none exist) in polynomial time. These results involve a connection to
the...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 20146

Unqiue Words: 2884

Suppose that an $m$-simplex is partitioned into $n$ convex regions having
disjoint interiors and distinct labels, and we may learn the label of any point
by querying it. The learning objective is to know, for any point in the
simplex, a label that occurs within some distance $\epsilon$ from that point.
We present two algorithms for this task: Constant-Dimension Generalised Binary
Search (CD-GBS), which for constant $m$ uses $poly(n, \log \left(
\frac{1}{\epsilon} \right))$ queries, and Constant-Region Generalised Binary
Search (CR-GBS), which uses CD-GBS as a subroutine and for constant $n$ uses
$poly(m, \log \left( \frac{1}{\epsilon} \right))$ queries.
We show via Kakutani's fixed-point theorem that these algorithms provide
bounds on the best-response query complexity of computing approximate
well-supported equilibria of bimatrix games in which one of the players has a
constant number of pure strategies. We also partially extend our results to
games with multiple players, establishing further query complexity bounds...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 21144

Unqiue Words: 3243

We study the problem of \emph{jamming} in multiple independent \emph{Gaussian
channels} as a zero-sum game. We show that in the unique Nash equilibrium of
the game the best-response strategy of the transmitter is the
\emph{waterfilling} to the sum of the jamming and the noise power in each
channel and the best-response strategy of the jammer is the \emph{waterfilling}
only to the noise power.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 2340

Unqiue Words: 629

We consider the problem of fairly dividing a set of items. Much of the fair
division literature assumes that the items are "goods" i.e., they yield
positive utility for the agents. There is also some work where the items are
"chores" that yield negative utility for the agents. In this work, we consider
more general scenarios where for any item, an agent may have negative or
positive utility for it. We show that whereas some of the positive axiomatic
and computational results extend to this more general setting, others do not.
We also point out several gaps in the literature regarding the existence of
allocations satisfying certain fairness and efficiency properties as well as
the computational complexity of computing such allocations.

more |
pdf
| html
None.

DO:
Fair allocation of combinations of indivisible goods and chores. https://t.co/fgHCmql7Wh

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8523

Unqiue Words: 1781

Massive open online courses pose a massive challenge for grading the
answerscripts at a high accuracy. Peer grading is often viewed as a scalable
solution to this challenge, which largely depends on the altruism of the peer
graders. Some approaches in the literature treat peer grading as a 'best-effort
service' of the graders, and statistically correct their inaccuracies before
awarding the final scores, but ignore graders' strategic behavior. Few other
approaches incentivize non-manipulative actions of the peer graders but do not
make use of certain additional information that is potentially available in a
peer grading setting, e.g., the true grade can eventually be observed at an
additional cost. This cost can be thought of as an additional effort from the
teaching staff if they had to finally take a look at the corrected papers post
peer grading. In this paper, we use such additional information and introduce a
mechanism, TRUPEQA, that (a) uses a constant number of instructor-graded
answerscripts to quantitatively measure the...

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 11630

Unqiue Words: 2453

Strong Stackelberg equilibrium (SSE) is the standard solution concept of
Stackelberg security games. As opposed to the weak Stackelberg equilibrium
(WSE), the SSE assumes that the follower breaks ties in favor of the leader and
this is widely acknowledged and justified by the assertion that the defender
can often induce the attacker to choose a preferred action by making an
infinitesimal adjustment to her strategy. Unfortunately, in security games with
resource assignment constraints, the assertion might not be valid; it is
possible that the defender cannot induce the desired outcome. As a result, many
results claimed in the literature may be overly optimistic. To remedy, we first
formally define the utility guarantee of a defender strategy and provide
examples to show that the utility of SSE can be higher than its utility
guarantee. Second, inspired by the analysis of leader's payoff by Von Stengel
and Zamir (2004), we provide the solution concept called the inducible
Stackelberg equilibrium (ISE), which owns the highest utility...

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 6

Total Words: 9756

Unqiue Words: 2283

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 72,893 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible